P1880[NOI1995]石子合并（区间DP）Gyibin的博客-

P1880 [NOI1995]石子合并
1880
在一个圆形操场的四周摆放 NN 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 NN 堆石子合并成 11 堆的最小得分和最大得分。

输入格式
数据的第 11 行是正整数 NN，表示有 NN 堆石子。

第 22 行有 NN 个整数，第 ii 个整数 a_ia
i
​
表示第 ii 堆石子的个数。

输出格式
输出共 22 行，第 11 行为最小得分，第 22 行为最大得分。

输入
4
4 5 9 4
输出
43
54

#include <cstdio> #include <cstdio> #include <algorithm> #include <cstring> #include <iostream> #include <vector> using namespace std; int dp[210][210]; //表示从i到j所要花费的代价。 int a[210],s[210]; int dp1[210][210]; int ans; int main() { int n;     cin>>n; for (int i = 1; i <= n; i++) {         cin >> a[i];         s[i] = s[i - 1] + a[i]; //前缀和 } for (int i = n + 1; i <= 2 * n; i++)         s[i] = s[i - 1] + a[i - n];//同上 for(int len=2;len<=n;len++){//枚举区间长度 for(int i=1,j=i+len-1;j<=2*n;i++,j++){//枚举左右端点             dp[i][j]=0x3f3f3f3f;//初始化第一个区间             dp1[i][j]=-1;//同上 for(int k=i;k<j;k++){             dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);             dp1[i][j]=max(dp1[i][j],dp1[i][k]+dp1[k+1][j]+s[j]-s[i-1]); } } } int minn=0x3f3f3f3f,maxx=-100; for(int i=1;i<=n;i++){//因为是环形的，所以最值不一定在（1，n）;          minn=min(minn,dp[i][i+n-1]);          maxx=max(maxx,dp1[i][i+n-1]); }     cout<<minn<<endl<<maxx; return 0; }