Polygon

题意：给定一个环，每个节点是一个数字，每条边是加号或者乘号。首先删除一条边，接下来重复下列方式进行游戏：1. 选取一条边，删除它。2. 把删除的边两端的数字按照符号合并为一个新的节点。直到没有边。

分析：简单的 Dp 问题，如果用 $f[i][j]$ 表示将环拆开后再复制一遍后，从 $i$ 号节点到 $j$ 号节点经过运算后的最大值，那么

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

$f[i][i+n-1]$ 的最大值即猥琐求

但是: 注意到: 题中说明运算中数字大小在 (-32768,32767) 区间内，所以说明有负数。两个负数的乘积可能为很大的正数。所以题中需要转移两个量：最大值和最小值。

令 $mn[i][j]$ 为从 $i$ 到 $j$ 所得的最小值， $mx[i][j]$ 为最大值，则

$mx[i][i+j]=max(mn[i][k]mn[k+1][i+j],mx[i][k]mx[k+1][i+j]);$

$mn[i][i+j]=min(mx[i][k]mn[k+1][i+j],mx[i][k]mn[k+1][i+j],mn[i][k]*mx[k+1][i+j]);$

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

#define MX 102
#define PLU 1
#define MUL 2

using namespace std;

int num[MX],cal[MX],n;
int mn[MX][MX],mx[MX][MX];

void input()
{
    char ch;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        ch=getchar();
        while(ch==' '||ch=='\n'||ch=='\r')ch=getchar();
        if(ch=='t')cal[i]=PLU;
        else if(ch=='x') cal[i]=MUL;
        scanf("%d",&num[i]);
        num[i+n]=num[i];
        cal[i+n]=cal[i];
    }
}

int main()
{
    input();
    for(int i=1;i<=n*2;i++)for(int j=1;j<=n*2;j++)mx[i][j]=-327699,mn[i][j]=327689;
    for(int i=1;i<=n*2;i++)mx[i][i]=mn[i][i]=num[i];
    for(int j=1;j<=n;j++)
    {
        for(int i=1;i+j<=n*2;i++)
        {
            for(int k=i;k<=i+j-1;k++)
            {
                if(cal[k+1]==PLU)
                {
                    mx[i][i+j]=max(mx[i][i+j],mx[i][k]+mx[k+1][i+j]);
                    mn[i][i+j]=min(mn[i][i+j],mn[i][k]+mn[k+1][i+j]);
                }
                else
                {
                    mx[i][i+j]=max(mx[i][i+j],mx[i][k]*mx[k+1][i+j]);
                    mx[i][i+j]=max(mx[i][i+j],mn[i][k]*mn[k+1][i+j]);
                    mn[i][i+j]=min(mn[i][i+j],mn[i][k]*mx[k+1][i+j]);
                    mn[i][i+j]=min(mn[i][i+j],mx[i][k]*mn[k+1][i+j]);
                    mn[i][i+j]=min(mn[i][i+j],mx[i][k]*mn[k+1][i+j]);
                }
            }
        }
    }
    int p=-3838383,mxpos[MX],pnum=0;
    for(int i=1;i<=n;i++)
    {
        if(mx[i][i+n-1]==p)mxpos[++pnum]=i;
        else if(mx[i][i+n-1]>p)p=mx[i][i+n-1],pnum=1,mxpos[pnum]=i;
    }
    printf("%d\n",p);
    for(int i=1;i<=pnum;i++)printf("%d ",mxpos[i]);
    return 0;
}

【题解】Polygon (IOI98) 动态规划 -boshi

于2017年5月18日2017年5月18日由boshi发布

Polygon

题意：给定一个环，每个节点是一个数字，每条边是加号或者乘号。首先删除一条边，接下来重复下列方式进行游戏：1. 选取一条边，删除它。2. 把删除的边两端的数字按照符号合并为一个新的节点。直到没有边。

分析：简单的 Dp 问题，如果用 $f[i][j]$ 表示将环拆开后再复制一遍后，从 $i$ 号节点到 $j$ 号节点经过运算后的最大值，那么

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

$f[i][i+n-1]$ 的最大值即猥琐求

但是: 注意到: 题中说明运算中数字大小在 (-32768,32767) 区间内，所以说明有负数。两个负数的乘积可能为很大的正数。所以题中需要转移两个量：最大值和最小值。

令 $mn[i][j]$ 为从 $i$ 到 $j$ 所得的最小值， $mx[i][j]$ 为最大值，则

$mx[i][i+j]=max(mn[i][k]mn[k+1][i+j],mx[i][k]mx[k+1][i+j]);$

$mn[i][i+j]=min(mx[i][k]mn[k+1][i+j],mx[i][k]mn[k+1][i+j],mn[i][k]*mx[k+1][i+j]);$

0 条评论

发表回复取消回复

【题解】Polygon (IOI98) 动态规划 -boshi

于2017年5月18日2017年5月18日由boshi发布

Polygon

题意：给定一个环，每个节点是一个数字，每条边是加号或者乘号。首先删除一条边，接下来重复下列方式进行游戏：1. 选取一条边，删除它。2. 把删除的边两端的数字按照符号合并为一个新的节点。直到没有边。

分析：简单的 Dp 问题，如果用 f[i][j]f[i][j]表示将环拆开后再复制一遍后，从 ii号节点到 jj号节点经过运算后的最大值，那么

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

f[i][i+n−1]f[i][i+n-1]的最大值即猥琐求

但是: 注意到: 题中说明运算中数字大小在 (-32768,32767) 区间内，所以说明有负数。两个负数的乘积可能为很大的正数。所以题中需要转移两个量：最大值和最小值。

令 mn[i][j]mn[i][j]为从 ii到 jj所得的最小值，mx[i][j]mx[i][j]为最大值，则

$mx[i][i+j]=max(mn[i][k]mn[k+1][i+j],mx[i][k]mx[k+1][i+j]);$

$mn[i][i+j]=min(mx[i][k]mn[k+1][i+j],mx[i][k]mn[k+1][i+j],mn[i][k]*mx[k+1][i+j]);$

0 条评论

发表回复 取消回复

分析：简单的 Dp 问题，如果用 $f[i][j]$ 表示将环拆开后再复制一遍后，从 $i$ 号节点到 $j$ 号节点经过运算后的最大值，那么

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

$f[i][i+n-1]$ 的最大值即猥琐求

令 $mn[i][j]$ 为从 $i$ 到 $j$ 所得的最小值， $mx[i][j]$ 为最大值，则

发表回复取消回复