1.合并石子
（1）排成一列的石子
这个与合并果子唯一的不同就是只能合并相邻的石子，所以贪不得（怎么所有类型的动规要先上来搞贪心，有点diss贪心的感觉）
f[i][j]表示i到j间合并的最大/最小得分；
核心
for(int len=2;len<=n;len++){//表示长度2到len时的最大
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;//i是起点，j是终点
for(int k=i;k<j;k++){//k是断点
f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+s[j]-s[i-1]);
}
}
}
点击查看代码
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1001;
int n;
int a[maxn],s[maxn];
int f[maxn][maxn];
int f1[maxn][maxn];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];//求前缀和
memset(f,0x7f,sizeof(f));
for(int i=1;i<=n;i++) {f[i][i]=0;}
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
for(int k=i;k<j;k++){
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+s[j]-s[i-1]);
}
}
}
cout<<f[1][n]<<endl<<f1[1][n];
}
t[i][j]表示i到j的和（用前缀和求）
简单来讲，在p(前一个）断点确定的情况下，后一个断点总是会靠在区间的两端；（不知道对不对）
目前好像就这些
1.定长度，计算前缀和
2.定起点终点
3.定断点