洛谷P4342 [IOI1998]Polygon 题解

题目链接：P4342 [IOI1998]Polygon

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

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

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

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

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

这里每条边的运算符旁边的数字为边的编号，不拿来计算

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

$3 \le n\le 50$

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

容易发现我们需要断环为链，然后区间dp

注意到存在负数，而负负得正，说明不是简单的区间dp

不难发现两个负的极小值之乘积对答案有更大贡献

考虑维护区间最大值的同时维护区间最小值

即，设 $f[i][j]$ 为区间 $[i,j]$ 的最大值，$g[i][j]$ 为区间 $[i,j]$ 的最小值

当符号为”加”时，显然有

$$\begin{aligned} f[i][j]=&\max_{i\le k < j}(f[i][j],f[i][k]+f[k+1][j]) \\g[i][j]=&\min_{i\le k < j}(g[i][j],g[i][k]+g[k+1][j]) \end{aligned}$$

当符号为”乘”时

因为我们并不知道最大值是否非负，直接把所有情况都列出即可

$$\begin{aligned} f[i][j]=&\max_{i\le k < j}(f[i][j],f[i][k]\times f[k+1][j],g[i][k]\times g[k+1][j],f[i][k]\times g[k+1][j],g[i][k]\times f[k+1][j])\\ g[i][j]=&\min_{i\le k < j}(g[i][j],f[i][k]\times f[k+1][j],g[i][k]\times g[k+1][j],f[i][k]\times g[k+1][j],g[i][k]\times f[k+1][j]) \end{aligned}$$

时间复杂度 $O(n^3)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
#define N (int)(120)
int n,a[N],f[N][N],g[N][N];
char op[N];
int max5(int a,int b,int c,int d,int e)
{return max(a,max(b,max(c,max(d,e))));}
int min5(int a,int b,int c,int d,int e)
{return min(a,min(b,min(c,min(d,e))));}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> op[i] >> a[i];
        op[i+n]=op[i];a[i+n]=a[i];
    }
    for(int i=1; i<=2*n; i++)
        for(int j=1; j<=2*n; j++)
            f[i][j]=-INF,g[i][j]=INF;
    for(int i=1; i<=2*n; i++)
        f[i][i]=g[i][i]=a[i];
    for(int len=1; len<=n; ++len)
        for(int i=1; i+len-1<=2*n; i++)
        {
            int j=i+len-1;
            for(int k=i; k<j; k++)
            {
                if(op[k+1]=='x')
                {
                    f[i][j]=max5(f[i][j],f[i][k]*f[k+1][j],g[i][k]*g[k+1][j],f[i][k]*g[k+1][j],g[i][k]*f[k+1][j]);
                    g[i][j]=min5(g[i][j],f[i][k]*f[k+1][j],g[i][k]*g[k+1][j],f[i][k]*g[k+1][j],g[i][k]*f[k+1][j]);
                }else
                {
                    f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
                    g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]);
                }
            }
        }
    int ans=-INF,ok=0;
    for(int i=1; i<=n; i++)
        ans=max(ans,f[i][i+n-1]);
    cout << ans << endl;
    for(int i=1; i<=n; i++)
        if(f[i][i+n-1]==ans)
        {
            if(!ok)ok=1,cout << i;
            else cout << " " << i;
        }
    cout << endl;
    return 0;
}