一.经典例题

题目地址：

【P1880】[NOI1995]石子合并 - 洛谷

二.分析

转移方程

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;

}