区间dp经典题 , 自己鸽了好久才做
显然这道题不同于 果子合并 那道题
我们设 dp[i][j] 表示从 i 到 j 这个区域内的最大/最小价值
然后就很显然 , 我们要从 i 到 j 中选一个断点 k , 然后（以max为例）
1 dp[i][j] = std::max (dp[i][j] , dp[i][k] + dp[k + 1][j] + sum(i, j));
其中sum(i,j)是 i 到 j 的石子总数（前缀和可做）
那怎么枚举呐？
1 for(int i = 1; i <= n; i++){ 2 for(int j = 1; j <= n; j++){ 3 for(int k = i; k < j; k++){ 4 dp[i][j] = std::max (dp[i][j] , dp[i][k] + dp[k + 1][j] + sum(i, j)); 5 } 6 } 7 }
这样？
Too Simple！
我们很容易发现一个问题 , 我们可能需要的 dp[k + 1][j] 是初始值而非这段区间的答案（k + 1 != j , 如果等于的话本来就应该是初始值）
那我们换一种思路 , 我们枚举 (j - i) 这个差值
那不就保证了转移所需的状态都存在了嘛
另外 , 这道题是个环 , 所以我们需要破环为链 , 具体做法看代码
1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<iostream> 6 #include<algorithm> 7 #define APART puts("----------------------") 8 #define debug 1 9 #define FILETEST 1 10 #define inf 310 11 #define ll long long 12 #define ha 998244353 13 #define INF 0x7fffffff 14 #define INF_T 9223372036854775807 15 #define DEBUG printf("%s %d\n",__FUNCTION__,__LINE__) 16 17 namespace chino{ 18 19 inline void setting(){ 20 #if FILETEST 21 freopen("_test.in", "r", stdin); 22 freopen("_test.me.out", "w", stdout); 23 #endif 24 return; 25 } 26 27 inline int read(){ 28 char c = getchar(), up = c; int num = 0; 29 for(; c < ‘0‘ || c > ‘9‘; up = c, c = getchar()); 30 for(; c >= ‘0‘ && c <= ‘9‘; num = (num << 3) + (num << 1) + (c ^ ‘0‘), c = getchar()); 31 return up == ‘-‘ ? -num : num; 32 } 33 34 int n; 35 int num[inf]; 36 int sum[inf]; 37 int dpmin[inf][inf]; 38 int dpmax[inf][inf]; 39 40 inline int main(){ 41 n = read(); 42 for(int i = 1; i <= n; i++) 43 num[i + n] = num[i] = read(); 44 for(int i = 1; i <= (n << 1); i++) 45 sum[i] = sum[i - 1] + num[i]; 46 for(int c = 1; c < n; c++){ 47 for(int i = 1, j = 1 + c; i < (n << 1) && j < (n << 1); i++, j = i + c){ 48 dpmin[i][j] = INF >> 1; 49 for(int k = i; k < j; k++){ 50 dpmin[i][j] = std::min (dpmin[i][j], dpmin[i][k] + dpmin[k + 1][j] + sum[j] - sum[i - 1]); 51 dpmax[i][j] = std::max (dpmax[i][j], dpmax[i][k] + dpmax[k + 1][j] + sum[j] - sum[i - 1]); 52 } 53 } 54 } 55 int ansmin = INF, ansmax = -INF; 56 for(int i = 1; i <= n; i++){ 57 ansmin = std::min (ansmin, dpmin[i][i + n - 1]); 58 ansmax = std::max (ansmax, dpmax[i][i + n - 1]); 59 } 60 printf("%d\n%d\n", ansmin, ansmax); 61 return 0; 62 } 63 64 }//namespace chino 65 66 int main(){return chino::main();}
原文：https://www.cnblogs.com/chiarochinoful/p/problem-noi-1995-shizihebing.html