P1880 石子合并 （区间DP）

• 题目

注意，题目是个环形，所以我们狗尾续貂 地再加上一个数组的长度，总长度为2*n。

• 分析

可以说是区间DP的最简单的应用了，用到了点前缀和。

参考博客我觉得讲得真的很清楚orz

区间DP入门

从区间DP说起，

什么是区间dp?

顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。

所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然可以求出终点。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。

模板：

for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }

• 代码

//P1880 石子合并 second
#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<stdio.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn=200+10; 
int n;

int num[maxn];
int dp1[maxn][maxn];
int dp2[maxn][maxn];
int w[maxn];

int main()
{
	memset(num,0,sizeof(num));
	memset(w,0,sizeof(w));
	memset(dp1,0,sizeof(dp1));
	memset(dp2,0,sizeof(dp2));
	 
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&num[i]);
		num[i+n]=num[i];
	}
	
	for(int i=1;i<=2*n;i++)
		w[i]=w[i-1]+num[i];
			
	for(int len=2;len<=n;len++)//区间长度
	{
		for(int l=1;l+len-1<2*n;l++)
		{
			int r=l+len-1;
			dp1[l][r]=inf;//初始化最大，求最小 
			dp2[l][r]=-inf;//最大 
			for(int k=l;k<r;k++)
			{
				dp1[l][r]=min(dp1[l][r],dp1[l][k]+dp1[k+1][r]+w[r]-w[l-1]);
				dp2[l][r]=max(dp2[l][r],dp2[l][k]+dp2[k+1][r]+w[r]-w[l-1]);
			}
		}
	 } 
	 int ans1=inf,ans2=-inf;
	 for(int i=1;i<=n;i++)
	 {
	 	ans1=min(ans1,dp1[i][i+n-1]);
	 	ans2=max(ans2,dp2[i][i+n-1]);
	 }
	 cout<<ans1<<endl<<ans2<<endl;
}

 这个主要的DP，k总是忘了+1.

左端点的可行范围，要靠右端点来控制

可行范围由于是环形，遍历到2*n

最后结果，因为是环形，dp[i][i+n-1] 中取最大值