============================================================
又是一道超经典的题目。 对于线性的合并石子问题，dp模型类似于“加括号”那类型的dp题目，设 f(i, j)为 将第i项到第j项合并得到的最优解 关键是，这题目是环形的。环形结构，经常采用双倍长度线性化手段，也就是说，把环形结构看成是长度为环的两倍的线性结构来处理。 环的长度是N，所以题目相当于有一排石子1....N+N，然后就可以用线性的石子合并问题的方法做了。 有个要注意的地方，f(i, j) 总是与 f(N +ｉ, N +j) 相等的，所以可以减少一些不必要的计算。
#include#include using namespace std;int _sum[205];int a[205];int N;int f[205][205];int g[205][205];int getSegmentSum(int i, int j) { return _sum[j] - _sum[i] + a[i];}int dp(int i, int j) { int & ans = f[i][j]; if (ans != -1) return ans; if (i == j) return ans = 0; if (i + 1 == j) return ans = getSegmentSum(i , j); if (i <= N && j <= N) return ans = dp(N + i, N + j); ans = 2000000000; int s = getSegmentSum(i, j); for (int k = i; k < j; ++k) { ans = min(ans, dp(i, k) + dp(k + 1, j) + s); } return ans;}int dp2(int i, int j) { int & ans = g[i][j]; if (ans != -1) return ans; if (i == j) return ans = 0; if (i + 1 == j) return ans = getSegmentSum(i , j); if (i <= N && j <= N) return ans = dp2(N + i, N + j); ans = -2000000000; int s = getSegmentSum(i, j); for (int k = i; k < j; ++k) { ans = max(ans, dp2(i, k) + dp2(k + 1, j) + s); } return ans;}void input() { int i, j; scanf("%d", &N); for (i = 1; i <= N; ++i) { scanf("%d", &(a[i])); } for (i = N + 1; i <= N + N; ++i) a[i] = a[i - N]; _sum[1] = a[1]; for (i = 2; i <= N + N; ++i) _sum[i] = a[i] + _sum[i - 1]; for (i = 0; i < 205; ++i) for (j = 0; j < 205; ++j) f[i][j] = g[i][j] = -1;}int main() { input(); int i, j; for (i = N + N; i >= 1; --i) for (j = i; j <= N + N; ++j) { dp(i, j); dp2(i, j); } int ans = 2000000000; for (i = 1; i <= N; ++i) { ans = min(ans, dp(i, i + N - 1)); } int ans2 = -2000000000; for (i = 1; i <= N; ++i) { ans2 = max(ans2, dp2(i, i + N - 1)); } printf("%d\n%d\n", ans, ans2); return 0;}