自动搬运

查看原文

来自洛谷，原作者为

	Kalista **

搬运于2025-08-24 21:59:11，当前版本为作者最后更新于2018-09-25 17:01:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

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

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

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

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

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

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

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

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

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

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

$f[i][j]=max(f[i][k]+f[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] > 0$时：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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]))))$

$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]))))$

记得初始化长度为$1$的情况，至于区间端点为$0$的情况，由于上面的这个式子里面四种组合都全部考虑到了就可以不管了。

然后就可以愉快的$A$掉啦!

$Code$：

#include<bits/stdc++.h>
#define lcy AKIOI
#define ll long long
const int inf=0x3f3f3f3f;
int n,ans=-inf;
int a[105];
int f[150][150],g[150][150];
char c[105];
int max(int x,int y){return (x>y)?(x):(y);}
int min(int x,int y){return (x<y)?(x):(y);}
int main(){
    scanf("%d\n",&n);//读入很诡异
    for(int i=1;i<=n;i++){
        scanf("%c %d",&c[i],&a[i]);getchar();
        a[n+i]=a[i];c[n+i]=c[i];//断环为链
    }
    for(int i=1;i<=(n<<1);i++){
        for(int j=1;j<=(n<<1);j++){
            f[i][j]=-inf,g[i][j]=inf;
        }
    }
    for(int i=1;i<=(n<<1);i++)f[i][i]=g[i][i]=a[i];
    for(int len=2;len<=n;len++){
        for(int i=1,j=len;j<=(n<<1);i++,j++){
            for(int k=i;k<j;k++){
                if(c[k+1]=='x'){
                    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]))));
                }
                else if(c[k+1]=='t'){
                    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]);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)ans=max(ans,f[i][i+n-1]);printf("%d\n",ans);
    for(int i=1;i<=n;i++)if(f[i][i+n-1]==ans)printf("%d ",i);
    return 0;
}