石子合并-区间DP
陈子骏
2018-04-02 18:44:09
```
//dp[l][r]=min/max(dp[i][k],dp[k+1][j])+sum[i][j]
//枚举左右端点 用前缀和维护sum；
#include<bits/stdc++.h>
using namespace std;
int dp1[501][501],dp2[501][501],n,max_,min_=9999,sum[501],num[501];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
num[i+n]=num[i]; sum[i]=sum[i-1]+num[i];
}
for(int i=n+1;i<=2*n;i++)
sum[i]=sum[i-1]+num[i];
for(int i=2*n-1;i;i--)
for(int j=i+1;j<=i+n;j++)
{
dp1[i][j]=9999;
for(int k=i;k<j;k++)
{
dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);
dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);
}
}
for(int i=1;i<=n;i++)
{
max_=max(max_,dp2[i][i+n-1]);
min_=min(min_,dp1[i][i+n-1]);
}
printf("%d\n%d\n",min_,max_);
}
```