这道题是经典的区间DP。因为它要求有每两个相邻的石子堆合并，所以很显然对于区间[l,r]内的情况，我们只要枚举端点k，之后把这左右两端的石子合并取最大/小即可。
之后，这题是环形怎么破？显然不需要枚举开头……直接把数组开成原来二倍长就可以。之后每次在取答案的时候只要计算一段长度为n的就可以了。
注意取大的DP数组可以全部清零，而取小的只有dp[i][i] = 0，其他全部赋成极大值。然后对于DP时数值的转移只要使用前缀和计算就可以。
看一下代码。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(‘\n‘) using namespace std; typedef long long ll; const int M = 205; int n,L,a[M],dp1[M][M],dp2[M][M],q[M],sum[M],minn = 1000000007,maxn; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) { if(ch == ‘-‘) op = -1; ch = getchar(); } while(ch >=‘0‘ && ch <= ‘9‘) { ans *= 10; ans += ch - ‘0‘; ch = getchar(); } return ans * op; } int main() { memset(dp1,127/3,sizeof(dp1)); n = read(); rep(i,1,n) { a[i] = a[i+n] = read(); dp1[i][i] = dp1[i+n][i+n] = 0; } rep(i,1,n<<1) sum[i] = sum[i-1] + a[i]; rep(j,1,n-1) { rep(i,1,(n<<1)-j) { rep(k,i,i+j-1) { dp1[i][i+j] = min(dp1[i][i+j],dp1[i][k] + dp1[k+1][i+j] + sum[i+j] - sum[i-1]); dp2[i][i+j] = max(dp2[i][i+j],dp2[i][k] + dp2[k+1][i+j] + sum[i+j] - sum[i-1]); } } } rep(i,1,n) minn = min(minn,dp1[i][i+n-1]),maxn = max(maxn,dp2[i][i+n-1]); printf("%d\n%d\n",minn,maxn); return 0; }
原文：https://www.cnblogs.com/captain1/p/9572144.html