P1880 [NOI1995] 石子合并【模板】区间DP

      ~~~~~      P1880 [NOI1995] 石子合并       ~~~~~      总题单链接

思路

      ~~~~~      任何一个区间最后都会合并为两个区间，然后再把这两个区间合并。

      ~~~~~      对于每一个区间，枚举最后剩下的两个区间即可转移。

      ~~~~~      具体操作时（求最小）：设 $dp[i]len]$ 表示以 $i$ 为左端点，长度为 $len$ 的区间合并为一堆石子的最小代价。

      ~~~~~      $dp[i][len]=min(dp[i][j-i+1],dp[j+1][i+len-j-1]),i\le j<i+len-1$。

      ~~~~~      求最大同理。

代码

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f
using namespace std;

ll n,ans,a[205],pre[205],dp[205][205];

signed main(){
	ios::sync_with_stdio(false);
	
	cin>>n;
	for(ll i=1;i<=n;i++)
		cin>>a[i],a[i+n]=a[i];
	for(ll i=1;i<=n*2;i++)pre[i]=pre[i-1]+a[i];
	
	// 求最小 
		
	memset(dp,0x3f,sizeof(dp));
	for(ll i=1;i<=n*2;i++)dp[i][1]=0;
	
	for(ll len=2;len<=n;len++)
		for(ll i=1;i+len-1<=n*2;i++){
			for(ll j=i;j<i+len-1;j++)
				dp[i][len]=min(dp[i][len],dp[i][j-i+1]+dp[j+1][i+len-j-1]);
			dp[i][len]+=pre[i+len-1]-pre[i-1];
		}
	
	ans=INF;
	for(ll i=1;i<=n;i++)
		ans=min(ans,dp[i][n]);
	cout<<ans<<endl;
	
	//求最大，其实就是把 min 换成 max，以及把初始化改一下 
	
	memset(dp,-0x3f,sizeof(dp));
	for(ll i=1;i<=n*2;i++)dp[i][1]=0;
	
	for(ll len=2;len<=n;len++)
		for(ll i=1;i+len-1<=n*2;i++){
			for(ll j=i;j<i+len-1;j++)
				dp[i][len]=max(dp[i][len],dp[i][j-i+1]+dp[j+1][i+len-j-1]);
			dp[i][len]+=pre[i+len-1]-pre[i-1];
		}
	
	ans=-INF;
	for(ll i=1;i<=n;i++)
		ans=max(ans,dp[i][n]);
	cout<<ans;
	
	return 0;
}