polygon题解-区间DP

#include <iostream>
#include <string.h>
using namespace std;
const int N=55;
typedef long long LL;
char ope[N<<1];
int dp[N<<1][N<<1],a[N<<1],res[N],cnt=0,ans=-0x3f3f3f3f,dp1[N<<1][N<<1];//最开始WA以为爆LL 或者inf了
/*
原本以为是水题，结果把自己坑了··
这个负数接触的太少了··  负数*负数得到的正数可能更大

思路：区间DP，令dp[i][j]表示把从i到j的部分合并之后得到的最大值
    每次去掉所有边中的一条边，考察按照剩下的所有边合并之后能得到的最大值
    因为数据范围只有50，所以直接暴力枚举去掉的边，时间复杂度O(n^4)
    dp方程很简单，dp[i][j]=max(dp[i][j],dp[i][k] _ dp[k+1][j]);
    看k和k+1之间的操作符是乘法还是加法即可
    但是维护最大值的过程中，可能出现两个负数的乘积比其他情况都要大的情况
    所以使用一个dp1[i][j]维护最小值
    在进行乘法更新dp的过程中，检查两个dp1最小值的乘积是不是比dp最大值要大

    然后是日常维护，dp的维护就是找最大值，
    求和时必然时两个最大值之和
    乘积时可能是最大值的乘积，也可能是两个最小值的乘积

    最小值dp1的维护稍微麻烦，
    求和时必然时两个最大值之和
    乘积时可能是两个最小值的乘积，也可能是一个最大值和一个最小值的乘积

    然后为了维护方便，因为每次去掉一条边之后还得顺次枚举剩下的边，相当于一个环，
    断环为链，开两倍维护即可，省的取模
*/
int main()
{
    //memset(dp,-0x3f,sizeof(dp));
    int n; cin>>n;
    for(int i=0;i<n;i++){
        cin>>ope[i]>>a[i];
        ope[i+n]=ope[i];
        a[i+n]=a[i];
    }
    for(int mov=0;mov<n;mov++){//去掉的边
        memset(dp,-0x3f,sizeof(dp));memset(dp1,0x3f,sizeof(dp1));
        for(int i=0;i<n;i++)
            dp[i][i]=dp[i+n][i+n]=a[i],dp1[i][i]=dp1[i+n][i+n]=a[i];
        for(int len=1;len<=n;len++){
            for(int i=mov;i<n+mov;i++){//更新n行 即所有点
                int j=i+len-1;
                for(int k=i;k<j;k++){
                    if(ope[k+1]=='t'){
                        dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
                        dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]);
                    }
                    else{
                        dp[i][j]=max(dp[i][j],dp[i][k]*dp[k+1][j]);
                        dp[i][j]=max(dp[i][j],dp1[i][k]*dp1[k+1][j]);
                        dp1[i][j]=min(dp1[i][j],dp1[i][k]*dp1[k+1][j]);
                        dp1[i][j]=min(dp1[i][j],dp1[i][k]*dp[k+1][j]);
                        dp1[i][j]=min(dp1[i][j],dp[i][k]*dp1[k+1][j]);
                    }

                }
            }
        }
        if(dp[mov][mov+n-1]>=ans){
            if(dp[mov][mov+n-1]>ans)
                cnt=0;
            ans=dp[mov][mov+n-1];
            res[cnt++]=mov;
        }


//        cout<<"图"<<endl;//输出检查
//        for(int i=0;i<n*2;i++){
//            for(int j=0;j<n*2;j++)
//                printf("%11d ",dp[i][j]);
//            cout<<endl;
//        }
//        cout<<endl;
    }


    cout<<ans<<endl;
    for(int i=0;i<cnt;i++)
        cout<<res[i]+1<<" ";
    cout<<endl;

    return 0;
}