石子合并《1》

 1 //CCTzhu 2020-6-17
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 const int maxn=110;
 5 const int inf=0x3f3f3f3f;
 6 int f1[maxn][maxn],f2[maxn][maxn],sum[maxn];
 7 int main(){
 8     int n;
 9     memset(f2,inf,sizeof(f2));//要求最小值，提前初始化;
10     scanf("%d",&n);
11     for(int i=1;i<=n;i++){
12         scanf("%d",&sum[i]);
13         sum[i]+=sum[i-1];
14         f2[i][i]=0;//注意下面for循环要用f[i][i]实际上是不能自己和自己合并的;
15     }
16     for(int d=2;d<=n;d++){//枚举长度
17         for(int i=1,j;(j=i+d-1)<=n;i++){
18             for(int k=i;k<j;k++){
19                 f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+sum[j]-sum[i-1]);
20                 f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+sum[j]-sum[i-1]);//----|>得益于上面的初始化;
21             }
22         }
23     }
24     printf("%dn%dn",f2[1][n],f1[1][n]);
25     return 0;
26 }