简洁的代码

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e2+5,inf=1<<29;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
int n,a[maxn],res[maxn],f[maxn][maxn][2];//i,j区间0为最高，1为最低 
char op[maxn];
int cal(int a,int b,char op) {
    if(op=='t') return a+b;
    else return a*b;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>op[i]>>a[i];
        op[i+n]=op[i],a[i+n]=a[i];
    }
    //init
    for(int i=1;i<=2*n;i++) {
        for(int j=i+1;j<=2*n;j++) {
            f[i][j][0]=-inf;
            f[i][j][1]=inf;
        }
    } 
    for(int i=1;i<=2*n;i++) 
        f[i][i][0]=f[i][i][1]=a[i];
    //dp
    for(int len=2;len<=n;len++) { //阶段 
        for(int i=1;i+len-1<=2*n;i++) { //左点位置 
            int j=i+len-1; //右点位置 
            for(int k=i;k<j;k++) { //决策 
                for(int x=0;x<=1;x++) for(int y=0;y<=1;y++) 
                f[i][j][0]=max(f[i][j][0],cal(f[i][k][x],f[k+1][j][y],op[k+1]) ) ,
                f[i][j][1]=min(f[i][j][1],cal(f[i][k][x],f[k+1][j][y],op[k+1]) ) ;
            } 
        }
    }
    int ans=0,len=0;
    for(int i=1;i<=n;i++) {
        if(ans<f[i][i+n-1][0]) {
            ans=f[i][i+n-1][0];
            len=0; res[++len]=i;
        } else if(ans==f[i][i+n-1][0]) {
            res[++len]=i;
        }
    }
    cout<<ans<<endl; 
    for(int i=1;i<=len;i++) 
        cout<<res[i]<<' '; 
    return 0;
}