本文主要是介绍洛谷 P1775 石子合并（弱化版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：区间DP
首先这其实是一个模板题，其次，这道题可能有人会觉得简单，但是我还是需要讲一下具体的思路，以方便自己的理解，和新手的初学。
对于一堆石子来说，我们需要知道，怎么样才能使这种代价变得最小，也就是在相邻的石子堆之中，我们需要遍历每一个区间，也就是区间的长度最多是N,意思也就是我们需要遍历这区间当中的每一个子区间，然后再一个一个去选，把全部的结果罗列出来之后我们才能知道这里的最佳答案在哪个地方才对。
代码的思路是这样的：第一重循环我们用来遍历区间的长度，区间的长度从2开始，我们的dp数组由于需要最小代价，所以需要初始化为无穷大才行。dp数组的含义就是[i,j]区间里面的合并的最小代价。然后，我们合并的时候需要找到最左边的区间指针，和最右边的区间指针，然后在这两个指针中间不断地断点，断点之后各自算出断点分出来的两个区间之后，合并他们的时候需要用到这个大区间的代价，也就是对于这整个区间的合并代价，我们需要用到前缀和。
剩下的两重循环就是这个过程，第二重循环简单来说就是判断左指针的位置，第三重循环就是对于这个区间的断点的判断。
上代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_map>
#include<set>
#define int long long
#define MAX 501
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int s[MAX];
int dp[MAX][MAX];
int a[MAX];
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n;_for(i, 1, n + 1) {cin >> a[i];}memset(dp, 0x3f, sizeof dp);for (int i = 1; i <= n; i++)dp[i][i] = 0;for (int i = 1; i <= n; i++) {s[i] = s[i - 1] + a[i];}int len = 0;for (int len = 2; len <= n;len++) {for (int l = 1; l + len - 1 <= n; l++) {int r = l + len - 1;for (int k = l; k < r; k++) {dp[l][r] = min(dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1],dp[l][r]);}}}cout << dp[1][n];return 0;
}这篇关于洛谷 P1775 石子合并（弱化版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
