一.经典例题
题目地址：
二.分析
转移方程
dp_max[i][j]=max(dp_max[i][k]+dp_max[k+1][j],dp_max[i][j])+sum(i,j);
dp_min[i][j]=min(dp_min[i][k]+dp_min[k+1][j],dp_min[i][j])+sum(i,j);
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
int n;
int a[1000005];
int dp_max[1005][1005];
int dp_min[1005][1005];
int sum[1005];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[n+i]=a[i];
}
for(int i=1;i<=n*2;i++)
{
sum[i]=sum[i-1]+a[i];
dp_max[i][i]=dp_min[i][i]=0;
}
for(int l=2;l<=n;l++)
{
for(int i=1;i<=2*n-l+1;i++)
{
int j=i+l-1;
dp_max[i][j]=0;
dp_min[i][j]=0x3f3f3f;
for(int k=i;k<j;k++)
{
dp_max[i][j]=max(dp_max[i][k]+dp_max[k+1][j],dp_max[i][j]);
dp_min[i][j]=min(dp_min[i][k]+dp_min[k+1][j],dp_min[i][j]);
}
dp_max[i][j]+=sum[j]-sum[i-1];
dp_min[i][j]+=sum[j]-sum[i-1];
}
}
int ans1=0,ans2=0x3f3f3f;
for(int i=1;i<=n;i++)
{
ans1=max(dp_max[i][i+n-1],ans1);
ans2=min(dp_min[i][i+n-1],ans2);
}
cout<<ans2<<endl<<ans1<<endl;
return 0;
}
