acwing283. 多边形

题目

题解

1.破环成链，将多边形拓展成一个链，并将这个链拓展一倍，这样就可以得到环中任意两个点的顺序。

2.f[l][r]表示长度从l到r的最大值，选择任意长度段时，可以将其从k处分成两段，那么此时最大值就可以由f[l][k]和f[k+1][r]得到。此时要注意乘法运算，两个大的数相乘不一定是最大的数，因为存在负数，所以要存下当前区间的最小值。

#include<iostream>
using namespace std;
const int N=110,INF=0x3f3f3f3f;
int n;
char c[N];
int w[N],f[N][N],g[N][N];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        char op;int x;
        cin>>op>>x;
        c[i]=c[i+n]=op;
        w[i]=w[i+n]=x;
    }
    for(int len=1;len<=n;len++){
        for(int l=1;l+len-1<=2*n;l++){
            int r=l+len-1;
            if(len==1)f[l][r]=g[l][r]=w[l];
            else {
                f[l][r]=-INF,g[l][r]=INF;
                for(int k=l;k<r;k++){
                    char op=c[k+1];
                    int maxl=f[l][k],minl=g[l][k],minr=g[k+1][r],maxr=f[k+1][r];
                    if(op=='t'){
                        f[l][r]=max(f[l][r],maxl+maxr);
                        g[l][r]=min(g[l][r],minl+minr);
                    }else{
                        int x1=maxl*maxr,x2=maxl*minr,x3=minl*maxr,x4=minl*minr;
                        f[l][r]=max(f[l][r],max(max(x1,x2),max(x3,x4)));
                        g[l][r]=min(g[l][r],min(min(x1,x2),min(x3,x4)));
                    }
                }
            }
        }
    }
    int res=-INF;
    for(int i=1;i<=n;i++)res=max(res,f[i][i+n-1]);
    cout<<res<<endl;
    for(int i=1;i<=n;i++){
        if(res==f[i][i+n-1])cout<<i<<" ";
    }
    
    return 0;
}