原题链接

题解

最近做的题目有点多，感觉没什么好讲的,某个最大值一定是由连续区间上的节点操作后得来的

\(Code\)

#include<bits/stdc++.h>
using namespace std;
int f[105][105][2];
int main()
{
    memset(f,-0x3f3f3f,sizeof f);
    int n;
    cin>>n;
    char op[105];
    int a[105];
    for(int i=1;i<=n;i++)
    {
        cin>>op[i]>>a[i];
        op[i+n]=op[i];
        a[i+n]=a[i];
    }

    int ans=-1e9;
    for(int start=1;start<=n;start++)//拆环成链恰好符合第一步remove的操作
    {
        for(int i=1;i<=2*n;i++) f[i][i][0]=f[i][i][1]=a[i];
        for(int d=2;d<=n;d++)
        {
            for(int l=start;l<=start+n-d+1;l++)
            {
                int r=l+d-1,mins=2e9;
                for(int mid=l;mid<r;mid++)
                {
                    f[l][r][1]=max(f[l][r][1],(op[mid+1]=='x')?max(f[l][mid][1]*f[mid+1][r][1],f[l][mid][0]*f[mid+1][r][0]):f[l][mid][1]+f[mid+1][r][1]);
                    //细节，由于乘法负负得正的存在，某个区间的最大值可能不是由最大值传递过来的，而是由最小的负值传过来的的
                    mins=min(mins,(op[mid+1]=='x')?min(f[l][mid][1]*f[mid+1][r][1],f[l][mid][0]*f[mid+1][r][0]):f[l][mid][0]+f[mid+1][r][0]);
                    //细节，由于没有覆盖过的最小值是-0x3f3f3f,所以如果想求最大值一样求会无法更新
                }
                f[l][r][0]=mins;
            }
        }
        ans=max(ans,f[start][start+n-1][1]);
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)  if(f[i][i+n-1][1]==ans)cout<<i<<" ";//op[i]代表i与前一个节点的操作
    return 0;
}