P4342 [IOI1998]Polygon —— 断链成环

多边形是一个玩家在一个有n个顶点的多边形上的游戏，如图所示，其中n＝4。每个顶点用整数标记，每个边用符号+（加）或符号*（乘积）标记。

第一步，删除其中一条边。随后每一步：

选择一条边连接的两个顶点V1和V2，用边上的运算符计算V1和V2得到的结果来替换这两个顶点。

游戏结束时，只有一个顶点，没有多余的边。

如图所示，玩家先移除编号为3的边。之后，玩家选择计算编号为1的边，然后计算编号为4的边，最后，计算编号为2的边。结果是0。

（翻译者友情提示：这里每条边的运算符旁边的数字为边的编号，不拿来计算）

编写一个程序，给定一个多边形，计算最高可能的分数。

输入格式

输入描述一个有n个顶点的多边形，它包含两行。第一行是数字n，为总边数。

第二行描述这个多边形，一共有2n个读入，每两个读入中第一个是字符，第二个是数字。

第一个字符为第一条边的计算符号(t代表相加，x代表相乘)，第二个代表顶点上的数字。首尾相连。

3 < = n < = 50

对于任何一系列的操作，顶点数字都在[-32768,32767]的范围内。

输出格式

第一行，输出最高的分数。在第二行，它必须写出所有可能的被清除后的边仍能得到最高得分的列表，必须严格递增。

感谢@2016c01 提供的翻译

输入输出样例

输入 #1

4
t -7 t 4 x 2 x 5

输出 #1

33
1 2

思路

事实上，这道题，绝大多数题解都有疏漏，原因是这道题的数据是真的水。。毕竟连最小值不要都可以得到808080。。至于错误的原因在下文有说明。

让我们重新开始吧，看到这道题，我们首要的两个问题：

1.如何处理这样一个环。

2.如何得到最开始删除的边。

对于第一个问题，很轻易地就可以想到断环成链，同时我们还可以发现，通过断环成链，我们把第二个问题就解决了，我们可以通过对最后的结果再来一次对最大值的遍历，输出即可。

开始考虑DPDPDP，首先我们可以很显然的得到一个区间DPDPDP的板子：

设f[i][j]f[i][j]f[i][j]表示[i,j][i,j][i,j]这一个区间内可以得到的最大得分，转移方程如下：

加法：f[i][j]=max(f[i][k]+f[k+1][j])f[i][j]=max(f[i][k]+f[k+1][j])f[i][j]=max(f[i][k]+f[k+1][j])

乘法：f[i][j]=max(f[i][k]×f[k+1][j])f[i][j]=max(f[i][k]\times f[k+1][j])f[i][j]=max(f[i][k]×f[k+1][j])

但是我们更往深入思考，因为有乘法的存在，且有负数，那就肯定会有一个负负得正的情况，所以我们还需要维护一个最小值。设这个最小值为g[i][j]g[i][j]g[i][j]

然后就是分情况讨论的时间：

首先对于加法的情况，因为不存在负负得正一类的情况存在，所以两者的转移方程是基本一样的，大区间的最大值等于合并的两个区间的最大值之和，最小值等于合并的两个区间的最小值之和：

f[i][j]=max(f[i][k]+f[k+1][j])f[i][j]=max(f[i][k]+f[k+1][j])f[i][j]=max(f[i][k]+f[k+1][j])

g[i][j]=min(g[i][k]+g[k+1][j])g[i][j]=min(g[i][k]+g[k+1][j])g[i][j]=min(g[i][k]+g[k+1][j])

其次对于乘法，这里就很容易有很多遗漏点，让我们一种种分情况讨论：

（啊这里原意想画图，但考虑到手画太丑，用软件又麻烦，实在不理解可以拿着笔画一下各种情况）

1.f[i][k],g[i][k],f[k+1][j],g[k+1][j]>01.f[i][k],g[i][k],f[k+1][j],g[k+1][j] > 01.f[i][k],g[i][k],f[k+1][j],g[k+1][j]>0时：

f[i][j]=max(f[i][k]×f[k+1][j])f[i][j]=max(f[i][k]\times f[k+1][j])f[i][j]=max(f[i][k]×f[k+1][j])

g[i][j]=min(g[i][k]×g[k+1][j])g[i][j]=min(g[i][k]\times g[k+1][j])g[i][j]=min(g[i][k]×g[k+1][j])

2.f[i][k],g[i][k],f[k+1][j]>0,g[k+1][j]<02.f[i][k],g[i][k],f[k+1][j] > 0,g[k+1][j] < 02.f[i][k],g[i][k],f[k+1][j]>0,g[k+1][j]<0时：

f[i][j]=max(f[i][k]×f[k+1][j])f[i][j]=max(f[i][k]\times f[k+1][j])f[i][j]=max(f[i][k]×f[k+1][j])

g[i][j]=min(f[i][k]×g[k+1][j])g[i][j]=min(f[i][k]\times g[k+1][j])g[i][j]=min(f[i][k]×g[k+1][j])

3.f[i][k],g[i][k]>0,f[k+1][j],g[k+1][j]<03.f[i][k],g[i][k] > 0,f[k+1][j],g[k+1][j] < 03.f[i][k],g[i][k]>0,f[k+1][j],g[k+1][j]<0时：

f[i][j]=max(g[i][k]×f[k+1][j])f[i][j]=max(g[i][k]\times f[k+1][j])f[i][j]=max(g[i][k]×f[k+1][j])

g[i][j]=min(f[i][k]×g[k+1][j])g[i][j]=min(f[i][k]\times g[k+1][j])g[i][j]=min(f[i][k]×g[k+1][j])

4.f[i][k],f[k+1][j],g[k+1][j]>0,g[i][k]<04.f[i][k],f[k+1][j],g[k+1][j] > 0,g[i][k] < 04.f[i][k],f[k+1][j],g[k+1][j]>0,g[i][k]<0时：

f[i][j]=max(f[i][k]×f[k+1][j])f[i][j]=max(f[i][k]\times f[k+1][j])f[i][j]=max(f[i][k]×f[k+1][j])

g[i][j]=min(g[i][k]×f[k+1][j])g[i][j]=min(g[i][k]\times f[k+1][j])g[i][j]=min(g[i][k]×f[k+1][j])

5.f[i][k],f[k+1][j]>0,g[i][k],g[k+1][j]<05.f[i][k],f[k+1][j] > 0,g[i][k],g[k+1][j] < 05.f[i][k],f[k+1][j]>0,g[i][k],g[k+1][j]<0时：

f[i][j]=max(f[i][k]×f[k+1][j],g[i][k]×g[k+1][j])f[i][j]=max(f[i][k]\times f[k+1][j],g[i][k]\times g[k+1][j])f[i][j]=max(f[i][k]×f[k+1][j],g[i][k]×g[k+1][j])

g[i][j]=min(f[i][k]×g[k+1][j],g[i][k]×f[k+1][j])g[i][j]=min(f[i][k]\times g[k+1][j],g[i][k]\times f[k+1][j])g[i][j]=min(f[i][k]×g[k+1][j],g[i][k]×f[k+1][j])

（此处就没分绝对值大小的情况了，可以感性理解一下。）

6.f[i][k]>0,g[i][k],f[k+1][j],g[k+1][j]<06.f[i][k] > 0,g[i][k],f[k+1][j],g[k+1][j] < 06.f[i][k]>0,g[i][k],f[k+1][j],g[k+1][j]<0时：

f[i][j]=max(g[i][k]×g[k+1][j])f[i][j]=max(g[i][k]\times g[k+1][j])f[i][j]=max(g[i][k]×g[k+1][j])

g[i][j]=min(f[i][k]×g[k+1][j])g[i][j]=min(f[i][k]\times g[k+1][j])g[i][j]=min(f[i][k]×g[k+1][j])

7.f[k+1][j],g[k+1][j]>0,f[i][k],g[i][k]<07.f[k+1][j],g[k+1][j] > 0,f[i][k],g[i][k] < 07.f[k+1][j],g[k+1][j]>0,f[i][k],g[i][k]<0时：

f[i][j]=max(f[i][k]×g[k+1][j])f[i][j]=max(f[i][k]\times g[k+1][j])f[i][j]=max(f[i][k]×g[k+1][j])

g[i][j]=min(g[i][k]×f[k+1][j])g[i][j]=min(g[i][k]\times f[k+1][j])g[i][j]=min(g[i][k]×f[k+1][j])

8.f[k+1][j]>0,f[i][k],g[i][k],g[k+1][j]<08.f[k+1][j] > 0,f[i][k],g[i][k],g[k+1][j] < 08.f[k+1][j]>0,f[i][k],g[i][k],g[k+1][j]<0时：

f[i][j]=max(g[i][k]×g[k+1][j])f[i][j]=max(g[i][k]\times g[k+1][j])f[i][j]=max(g[i][k]×g[k+1][j])

g[i][j]=min(g[i][k]×f[k+1][j])g[i][j]=min(g[i][k]\times f[k+1][j])g[i][j]=min(g[i][k]×f[k+1][j])

9.f[i][k],g[i][k],f[k+1][j],g[k+1][j]<09.f[i][k],g[i][k],f[k+1][j],g[k+1][j] < 09.f[i][k],g[i][k],f[k+1][j],g[k+1][j]<0时：

f[i][j]=max(g[i][k]×g[k+1][j])f[i][j]=max(g[i][k]\times g[k+1][j])f[i][j]=max(g[i][k]×g[k+1][j])

g[i][j]=min(f[i][k]×f[k+1][j])g[i][j]=min(f[i][k]\times f[k+1][j])g[i][j]=min(f[i][k]×f[k+1][j])

（~~做了一个下午脑袋都要炸了，~~如果有BUGBUGBUG欢迎指出）

虽然说情况很多，但事实上你可以压成两行，不用特判。。（懒）

f[i][j]=max(f[i][j],max(f[i][k]×f[k+1][j],max(g[i][k]×g[k+1][j],max(f[i][k]×g[k+1][j],g[i][k]×f[k+1][j]))))f[i][j]=max(f[i][j],max(f[i][k]\times f[k+1][j],max(g[i][k]\times g[k+1][j],max(f[i][k]\times g[k+1][j],g[i][k]\times f[k+1][j]))))f[i][j]=max(f[i][j],max(f[i][k]×f[k+1][j],max(g[i][k]×g[k+1][j],max(f[i][k]×g[k+1][j],g[i][k]×f[k+1][j]))))

g[i][j]=min(g[i][j],min(f[i][k]×f[k+1][j],min(g[i][k]×g[k+1][j],min(f[i][k]×g[k+1][j],g[i][k]×f[k+1][j]))))g[i][j]=min(g[i][j],min(f[i][k]\times f[k+1][j],min(g[i][k]\times g[k+1][j],min(f[i][k]\times g[k+1][j],g[i][k]\times f[k+1][j]))))g[i][j]=min(g[i][j],min(f[i][k]×f[k+1][j],min(g[i][k]×g[k+1][j],min(f[i][k]×g[k+1][j],g[i][k]×f[k+1][j]))))

记得初始化长度为111的情况，至于区间端点为000的情况，由于上面的这个式子里面四种组合都全部考虑到了就可以不管了文章来源地址https://www.toymoban.com/news/detail-405137.html

代码

#include<bits/stdc++.h>
using namespace std;

const int MAX_SIZE = 110;

#define ruan main

struct edge
{
    char c;
    int num;
};

int dp[MAX_SIZE][MAX_SIZE];
int g[MAX_SIZE][MAX_SIZE];
edge edges[MAX_SIZE];

int ruan()
{
    memset(dp, 0, sizeof(dp));
    int n;
    cin >> n;
    for(int i = 1; i <= n * 2; i++)
        for(int j = 1; j <= n * 2; j ++) {
            g[i][j] = INT_MAX;
            dp[i][j] = -INT_MAX + 1;
        }
    for(int i = 1; i <= n; i ++)
    {
        cin >> edges[i].c >> edges[i].num;
        edges[i + n] = edges[i];
        dp[i][i] = dp[i + n][i + n] = g[i + n][i + n] = g[i][i] = edges[i].num;
    }

    int maxn = -INT_MAX + 1;

    for(int j = 2; j <= n * 2; j++)
        for(int i = j - 1; i >= 1 && j - i <= n - 1; i--)
            for(int k = i; k <= j - 1; k++)
            {
                if(edges[k + 1].c == 't')
                {
                    g[i][j] = min(g[i][j], g[i][k] + g[k + 1][j]);
                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    if(j - i == n - 1)
                        maxn = max(maxn, dp[i][j]);
                }
                else
                {
                    dp[i][j]=max(dp[i][j],max(dp[i][k] * dp[k+1][j],max(g[i][k] * g[k+1][j],max(dp[i][k] * g[k+1][j],g[i][k] * dp[k+1][j]))));
                    g[i][j]=min(g[i][j],min(dp[i][k] * dp[k+1][j],min(g[i][k] * g[k+1][j],min(dp[i][k] * g[k+1][j],g[i][k] * dp[k+1][j]))));
                    if(j - i == n - 1)
                        maxn = max(maxn, dp[i][j]);
                }
            }
    cout << maxn << endl;
    for(int i = 1; i <= n; i ++)
        if(dp[i][i + n - 1] == maxn)
            cout << i << ' ' ;
}

到了这里，关于P4342 [IOI1998]Polygon —— 断链成环的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！