P1880 [NOI1995]石子合并（区间DP）

题目链接：https://www.luogu.org/problemnew/show/P1880

题目大意：中文题目

具体思路：和上一篇的思路是差不多的，也是对于每一个小的区间进行处理，然后再归并到大区间上。

这里的递推式：dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];

AC代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn = 4e2+100;
const int mod =1e6;
# define LL_inf 0x3f3f3f3f3f3f3f
int dp1[maxn][maxn];
int dp2[maxn][maxn];
int sum[maxn],a[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
a[i+n]=a[i];
}
for(int i=n+1;i<=2*n;i++){
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++){
for(int j=1,pos=j+i;j<2*n&&pos<2*n;j++,pos=j+i){
dp1[j][pos]=inf;
for(int k=j;k<pos;k++){//注意这里不能等于，因为一个数的时候应该是按照0来算的
dp1[j][pos]=min(dp1[j][pos],dp1[j][k]+dp1[k+1][pos]+sum[pos]-sum[j-1]);
dp2[j][pos]=max(dp2[j][pos],dp2[j][k]+dp2[k+1][pos]+sum[pos]-sum[j-1]);
}
}
}
int minn=inf,maxx=0;
for(int i=1;i<=n;i++){
minn=min(minn,dp1[i][i+n-1]);
maxx=max(maxx,dp2[i][i+n-1]);
}
printf("%d
%d
",minn,maxx);
return 0;
}