环形石子合并问题。
有一种方法是取模，而如果空间允许的话(或者滚动数组)，可以把长度为n个换拓展成长为2n-1的直线。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int maxn = 2000 + 10; 9 const int INF = 0x3f3f3f3f; 10 11 int n; 12 13 int a[maxn], sum[maxn]; 14 int d[maxn][maxn], s[maxn][maxn]; 15 16 int main() 17 { 18 while(scanf("%d", &n) == 1 && n) 19 { 20 for(int i = 1; i <= n; i++) scanf("%d", a + i); 21 for(int i = n + 1; i < n * 2; i++) a[i] = a[i - n]; 22 for(int i = 1; i < n * 2; i++) sum[i] = sum[i - 1] + a[i]; 23 24 for(int i = 1; i + 1 < n * 2; i++) 25 { 26 s[i][i+1] = i; 27 d[i][i+1] = a[i] + a[i+1]; 28 } 29 30 for(int l = 3; l <= n; l++) 31 { 32 for(int i = 1; i + l - 1 < n * 2; i++) 33 { 34 int j = i + l - 1; 35 d[i][j] = INF; 36 for(int k = s[i][j-1]; k <= s[i+1][j]; k++) 37 { 38 int t = d[i][k] + d[k+1][j] + sum[j] - sum[i-1]; 39 if(t < d[i][j]) 40 { 41 d[i][j] = t; 42 s[i][j] = k; 43 } 44 } 45 } 46 } 47 48 int ans = INF; 49 for(int i = 1; i <= n; i++) ans = min(ans, d[i][i+n-1]); 50 printf("%d ", ans); 51 } 52 53 return 0; 54 }