多边形【推荐】

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;
}