#include <string.h>

#include <iostream>

#include <math.h>

using namespace std;

const int maxn=19950420;

int n,a[230]={0},sum[110][110]={0},fa[110][110]={0},fb[110][110]={0};

int zuobiao(int x)

{if(x>n)return x-n;return n;}

int min(int a,int b){return a<b?a:b;}

main()

{

cin>>n;

for(int i=1;i<=n;i++)scanf("%d",&a[i]);

for(int i=n+1;i<=2*n;i++)a[i]=a[i-n];//初始化a[i]

for(int i=1;i<=n;i++)sum[i][1]=a[i];

for(int i=1;i<=n;i++)

for(int j=2;j<=n;j++)

sum[i][j]=sum[i][j-1]+a[i+j-1];//初始化sum。从i,合并到J的合并柿子树

for(int j=2;j<=n;j++)//以合并堆数为阶段

for(int i=1;i<=n;i++) {fa[i][j]=maxn;fb[i][j]=-maxn;

for(int k=1;k<=j-1;k++){

int x=zuobiao(i+k);

fa[i][j]=min(fa[i][j],(fa[i][k]+fa[x][j-k]+sum[i][j]));

fb[i][j]=max(fb[i][j],(fb[i][k]+fb[x][j-k]+sum[i][j]));

}

}

int min1=maxn,max1=-maxn;

for(int i=1;i<=n;i++)

{

min1=min(min1,fa[i][n]);

max1=max(max1,fb[i][n]);

}

cout<<min1<<endl<<max1;

//system("pause");

}

动归方程 最小值为例

f[i,j]=min(f[i,k]+f[i+k]+sum[i,j])(1<=k<=j-1)

f[i,j]代表从第I堆开始，合并接下来J堆的最小值

最大值反过来……我真不明白我为什么错了

249毫秒

测试结果1: 通过本测试点|有效耗时157ms

测试结果2: 通过本测试点|有效耗时46ms

测试结果3: 测试结果错误.错误结果为:74

119

正确结果应为:84

125

测试结果4: 通过本测试点|有效耗时46ms

测试结果5: 测试结果错误.错误结果为:153

296

正确结果应为:153

304

测试结果6: 测试结果错误.错误结果为:97

159

正确结果应为:110

171

测试结果7: 测试结果错误.错误结果为:280

475

正确结果应为:275

475

测试结果8: 测试结果错误.错误结果为:1114

4948

正确结果应为:1289

5081

测试结果9: 测试结果错误.错误结果为:4938

24021

正确结果应为:5913

24595

测试结果10: 测试结果错误.错误结果为:10162

94401

正确结果应为:12533

95356