洛谷P4342 [IOI1998]Polygon 题解

题目链接：P4342 [IOI1998]Polygon

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

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

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

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

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

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

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

3 ≤ n ≤ 50 3 le nle 50 3≤n≤50

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

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

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

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

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

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

当符号为"加"时，显然有
f [ i ] [ j ] = max ⁡ i ≤ k < j ( f [ i ] [ j ] , f [ i ] [ k ] + f [ k + 1 ] [ j ] ) g [ i ] [ j ] = min ⁡ i ≤ k < j ( g [ i ] [ j ] , g [ i ] [ k ] + g [ k + 1 ] [ j ] ) begin{aligned} f[i][j]=&max_{ile k < j}(f[i][j],f[i][k]+f[k+1][j]) \g[i][j]=&min_{ile k < j}(g[i][j],g[i][k]+g[k+1][j]) end{aligned} f[i][j]=g[i][j]=​i≤k

当符号为"乘"时

因为我们并不知道最大值是否非负，直接把所有情况都列出即可
f [ i ] [ j ] = max ⁡ i ≤ k < j ( 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 ] = min ⁡ i ≤ k < j ( 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 ] ) begin{aligned} f[i][j]=&max_{ile 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_{ile 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} f[i][j]=g[i][j]=​i≤k 时间复杂度 O ( n 3 ) O(n^3) O(n3)

代码：

#include 
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
                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;
}

转载请说明出处