POJ1179 Polygon（区间dp）

蔚落 2021-11-29 14:56 335阅读 0赞

## 题意：多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“\*”。所有边依次用整数从1到n编号，游戏第1步，将一条边删除，随后n-1步按以下方式操作   (1)选择一条边E以及由E连接着的2个顶点V1和V2   (2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点   最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。 ##

## 分析：《算法竞赛进阶指南》P284-286。 ##

## 代码： ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    using namespace std;
    const int M = 60;
    int n,a[2*M],f[2*M][2*M],f1[2*M][2*M];
    char b[2*M];
    int main()
    {
    	memset(f,-0x3f,sizeof f);
    	memset(f1,0x3f,sizeof f1);
    	scanf("%d",&n);
    	for(int i = 1; i <= n; i++)
    	getchar(),scanf("%c%d",&b[i],&a[i]),b[i+n] = b[i],a[i+n] = a[i];
    	for(int i = 1; i <= 2*n;i ++) f1[i][i] = f[i][i] = a[i];
    		for(int j = 2; j <= n;j++)
    			for(int k = 1; j + k - 1 <= 2 * n; k++)
    				for(int l = k+1;l <= j + k - 1; l++)
    				{
    
    					if(b[l] == 't')
    					{
    						f[k][j+k-1] = max(f[k][j+k-1],f[k][l-1] + f[l][j+k-1]);
    						f1[k][j+k-1] = min(f1[k][j+k-1],f1[k][l-1] + f1[l][j+k-1]);
    					}
    					else
    					{
    						f[k][j+k-1] = max(f[k][j+k-1],f[k][l-1] * f[l][j+k-1]);
    						f[k][j+k-1] = max(f[k][j+k-1],f1[k][l-1] * f1[l][j+k-1]);
    						f1[k][j+k-1] = min(f1[k][j+k-1],f1[k][l-1] * f1[l][j+k-1]);
    						f1[k][j+k-1] = min(f1[k][j+k-1],f1[k][l-1] * f[l][j+k-1]);
    						f1[k][j+k-1] = min(f1[k][j+k-1],f[k][l-1] * f1[l][j+k-1]);
    						f1[k][j+k-1] = min(f1[k][j+k-1],f[k][l-1] * f[l][j+k-1]);
    					}
    				}
    	int maxx = -0x7fffffff;
    	for(int i = 1; i <= n; i++)
    	maxx = max(maxx,f[i][i+n-1]);
    	printf("%d\n", maxx);
    	for(int i = 1; i <= n; i++)
    		if(f[i][i+n-1] == maxx)
    		printf("%d ",i);
    	return 0;
    }