题目：石子合并
思路：
断环为链。
sum[i]为原序列的前缀和。
令f[i,j]为一段以i为起点长度为j的石子合并需要的最小代价。
转移方程：
f[i][j]=min(f[i][j],f[i][k-i+1]+f[k+1][ed-k]+sum[ed]-sum[i-1]);其中，k为划分点，ed为这一段石子的末位置，即i+j-1。
主要的思想差不多就是枚举一个点把当前这段石子分为两部分，这一段的最小代价就是每次划分后的两段代价之和加上合并需要的代价的最小值。
最大值g(i,j)同理可求。
f，g可在同一函数中求得。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 200
#define inf (1<<29)int n;
int a[maxn+5]= {0},sum[maxn+5]= {0}; //原数据，前缀和int f[maxn+5][maxn+5]= {0},g[maxn+5][maxn+5]= {0}; //f(i,j)以i为起点长度为j的状态的最小代价,g同理为最大代价int fcmp(const int& a1,const int& a2,const int& opr){if((a1<a2)^opr) return a1;return a2;
}int dp(int ff[maxn+5][maxn+5],int cmp) {for(int j=2; j<=n; j++) { //当前状态石子的长度for(int i=1; i<=n-j+1; i++) { //当前状态石子的起点int ed=i+j-1;for(int k=i; k<ed; k++) { //断开的位置，属于前半段 ff[i][j]=fcmp(ff[i][j],ff[i][k-i+1]+ff[k+1][ed-k]+sum[ed]-sum[i-1],cmp);}}}int s=inf-cmp*inf;for(int i=1;i<=n/2;i++) s=fcmp(s,ff[i][n/2],cmp);return s;
}int main() {scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%d",&a[i]),a[i+n]=a[i]; //断环为链n*=2;for(int i=1; i<=n; i++) sum[i]=a[i]+sum[i-1];//初始化for(int i=1;i<=n;i++) for(int j=2;j<=n;j++)f[i][j]=inf;int ans1=dp(f,0),ans2=dp(g,1);printf("%d\n%d",ans1,ans2);return 0;
}