多邊形【推薦】

Description

多邊形是一個單人玩的遊戲，開始時有一個N個頂點的多邊形。如圖，這裡N=4。每個頂點有一個整數标記，每條邊上有一個“+”号或“*”号。邊從1編号到N。

第一步，一條邊被拿走；随後各步包括如下：

選擇一條邊E和連接配接着E的兩個頂點V1和 V2；

得到一個新的頂點，标記為V1與V2通過邊E上的運算符運算的結果。

最後，遊戲中沒有邊，遊戲的得分為僅剩餘的一個頂點的值。

寫一個程式，對于給定一個多邊形，計算出可能的最高得分以及操作方法。

Solution

這道題的方法就是區間DP，首先枚舉删掉那條邊，然後在做區間DP。

要注意的是在區間DP的時候不僅要記錄最大值，還要記錄最小值

為什麼呢？

看一組資料就清楚了：

5

t -9 x -4 t -9 t -9 t -9

如果不記錄最小值，隻記錄最大值，他在算的時候會先算 -9 x -4 ，然後再算加，這樣子算出的結果并不是最大。

我們先把右邊的值相加，在相乘，結果是最大的。

到這裡，這道題的思路就這麼多了，如果有不懂區間DP是什麼的，自己就去學一下。

code

#include<bits/stdc++.h>
using namespace std;
int n,dp[51][51],f[51][51],a[51],b[51],p[51],ans,maxn,ansn[51];
char ch;
int in()
{
	char cha=getchar();
	int s=0;
	while(cha>'9'||cha<'0') cha=getchar();
	while(cha<='9'&&cha>='0') s=s*10+ch-'0',cha=getchar();
	return s;
}
int main()
{
	n=in();
	for(int i=1;i<=n;i++)
	{
		ch=getchar();
		while(ch!='t'&&ch!='x') ch=getchar();
		if(ch=='t') a[i]=1;
		else a[i]=2;
		b[i]=in();
	}
	for(int i=1;i<=n;i++)
	{
		memset(dp,-9,sizeof(dp));
		memset(f,9,sizeof(f));
		for(int j=1;j<n;j++) p[j]=a[(i+j-1)%n+1],dp[j][j]=f[j][j]=b[(i+j-2)%n+1];
		dp[n][n]=f[n][n]=b[(i+n-2)%n+1];
		for(int j=1;j<=n;j++)
		{
			for(int l=1;l<=n-j+1;l++)
			{
				int x=l,y=l+j-1;
				for(int k=x+1;k<=y;k++)
					if(p[k-1]==1) dp[x][y]=max(dp[x][y],dp[x][k-1]+dp[k][y]),f[x][y]=min(f[x][k-1]+f[k][y],f[x][y]);
					else dp[x][y]=max(dp[x][y],max(f[x][k-1]*f[k][y],dp[x][k-1]*dp[k][y])),f[x][y]=min(f[x][y],min(f[x][k-1]*f[k][y],dp[x][k-1]*dp[k][y]));
			}
		}
		if(dp[1][n]==maxn) ans++,ansn[ans]=i;
		if(dp[1][n]>maxn) maxn=dp[1][n],ans=1,memset(ansn,0,sizeof(ansn)),ansn[ans]=i;
	}
	printf("%d\n",maxn);
	for(int i=1;i<=ans;i++) printf("%d ",ansn[i]);
	return 0;
}