http://mail.bashu.cn:8080/BSoiOnline/showproblem?problem_id=1646
转移方程：
f[i][j]=max{f[i][k]+f[k+1][j]}+sum[j]-sum[i-1] (i<=k<j)
f[i][j]代表从第i堆到第j堆石子所得到的最大分数。sum[j]-sum[i-1]是从第i堆到第j堆
石子的总和。最终结果存在f[1][n]中。求最小值时道理一样。而我直接用这样一组循环：
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
最终显然不会达到目的，这样状态是无法转移的，因为用来得到本阶段的前面阶段都还未
求出来。可以用记忆化搜索达到目的。
另外一种写法是枚举石子的堆数，这样就解决了上面的问题。
代码
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 int f[101][101],n,a[101],sum[101]={0},min,max;
5
6 int main(){
7 int i,j,k,t;
8 while(scanf("%d",&n)!=EOF){
9 for(i=1;i<=n;i++)
10 {
11 scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];
12 }
13
14 memset(f,0,sizeof(f));
15 for(i=1;i<=n;i++)
16 for(j=1;j<=n-i+1;j++)
17 {
18 t=j+i-1;
19 for(k=j;k<t;k++)
20 if(f[j][t]<f[j][k]+f[k+1][t]+sum[t]-sum[j-1])
21 f[j][t]=f[j][k]+f[k+1][t]+sum[t]-sum[j-1];
22 }
23 max=f[1][n];
24
25 for(i=1;i<=n;i++)
26 {
27 for(j=i+1;j<=n;j++)
28 f[i][j]=1000000;
29 f[i][i]=0;
30 }
31 for(i=1;i<=n;i++)
32 for(j=1;j<=n-i+1;j++)
33 {
34 t=j+i-1;
35 for(k=j;k<t;k++)
36 if(f[j][t]>f[j][k]+f[k+1][t]+sum[t]-sum[j-1])
37 f[j][t]=f[j][k]+f[k+1][t]+sum[t]-sum[j-1];
38 }
39 min=f[1][n];
40 printf("%d %d\n",min,max);
41 }
42 return 0;
43 }
44