POJ1179 Polygon（区间dp）-蒲公英云

POJ1179 Polygon（区间dp）

蔚落 2021-11-29 14:56 459阅读 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;
}