题解 [IOI1998]Polygon

题目描述

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

1

第一步,删除其中一条边。随后每一步:

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

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

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

(翻译者友情提示:这里每条边的运算符旁边的数字为边的编号,不拿来计算)

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

输入格式

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

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

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

3 < = n < = 50

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

输出格式

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

Solution

这道题其实是一道典型的区间dp。
区间dp的一般做法是 枚举区间长度,然后对任意长度为枚举值区间进行dp的转移。
在本题中,我们定义 $f[i][j]$表示当前的区间为$[i,j]$在运算后的最大值。$g[i][j]$表示当前区间为$[i,j]$在运算后的最小值。

由于题目中要求我们要删去一条边,我们很自然的能够想到破环为链。直接把区间变为两倍,取其中连续的n个数进行运算。

对于每一个区间,我们对其中的每一条边进行枚举,把当前区间分为两个区间。且这两个区间由一个运算符连接。

那么在转移中就有多种情况,需要对乘法和加法进行分别考虑。
转移方程如下:
乘法:
$f[l][r]=max(f[l][r],f[l][k]*f[k+1][r]);$

$f[l][r]=max(f[l][r],f[l][k]*g[k+1][r]);$

$f[l][r]=max(f[l][r],g[l][k]*f[k+1][r]);$

$f[l][r]=max(f[l][r],g[l][k]*g[k+1][r]);$

$g[l][r]=min(g[l][r],f[l][k]*f[k+1][r]);$

$g[l][r]=min(g[l][r],f[l][k]*g[k+1][r]);$

$g[l][r]=min(g[l][r],g[l][k]*f[k+1][r]);$

$g[l][r]=min(g[l][r],g[l][k]*g[k+1][r]);$

加法的转移与上面基本一样,这里就不写了。
最后只要判断和统计一下答案就做完了

code:

发表评论