區間dp–P1880環狀石子合并題解

傳送門

題目描述

在一個圓形操場的四周擺放N堆石子,現要将石子有次序地合并成一堆.規定每次隻能選相鄰的2堆合并成新的一堆，并将新的一堆的石子數，記為該次合并的得分。

試設計出1個算法,計算出将N堆石子合并成1堆的最小得分和最大得分.

輸入格式

資料的第1行試正整數N,1≤N≤100,表示有N堆石子.第2行有N個數,分别表示每堆石子的個數.

輸出格式

輸出共2行,第1行為最小得分,第2行為最大得分.

輸入輸出樣例

輸入 #1 複制

4

4 5 9 4

輸出 #1 複制

43

54

##題解##

1.題目要求求區間内的最大值以及最小值，很明顯就需要通過子區間的狀态傳遞來實作動規操作了。

2.本題有一個很重要的點。就是該資料是呈環狀的。

也就是說我們dp得到的答案是這樣的： dp[i][i+n-1]。且1<=i<=n。而并不是一般dp的：dp[1][n];

那這個問題怎麼解決呢？goodquestion。直接将我們的dp邊界擴大一倍。

拆環成鍊。

3.dp方程其實很簡單。

在我們的區間i，j中枚舉一個k來求得最小/最大值

b數組裝得是字首和

dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+b[j]-b[i-1]);
	dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+b[j]-b[i-1]);
           

4.附上AC代碼+注釋、

//#include<bits/stdc++.h>
#include<iostream>  
#include<cstdio>  
#include<cmath> 
#define maxn 205 
using namespace std;
int dp1[maxn][maxn];
int dp2[maxn][maxn];
int a[305];
int b[305]; 
int n;
const int inf = 1e9;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[n+i]=a[i];//拆環成鍊 
	}	
	for(int i=1;i<=n*2;i++)
	{
		b[i]=b[i-1]+a[i];// 
	}
 
	for(int l=2;l<=n;l++)//區間長度 
	{
		for(int i=1,j;(j=i+l-1)<=2*n;i++)// 因為是環是以邊界為2*n 
		{
			dp1[i][j]=999999999;  
			for(int k=i;k<j;k++)
			{
				dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+b[j]-b[i-1]);
				dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+b[j]-b[i-1]);
			}
		}
	}
	int f1=1e9+1;
	int f2=-10;
	for(int i=1;i<=n;i++)
	{
		f1=min(dp1[i][i+n-1],f1);
		f2=max(dp2[i][i+n-1],f2);
	}
	cout<<f1<<endl<<f2;
	return 0;
}