Lee • 4个月前
using namespace std; int a[101]; char c[101]; int dp1[101][101],dp2[101][101]; int main(){
int n;
cin>>n;
memset(dp1,0xf0,sizeof dp1);
memset(dp2,0x3f,sizeof dp2);
for(int i=1;i<=n;i++){
cin>>c[i]>>a[i];
c[i+n]=c[i];
a[i+n]=a[i];
dp1[i][i]=dp2[i][i]=dp1[i+n][i+n]=dp2[i+n][i+n]=a[i];
}
for(int i=1;i<=n;i++){
for(int l=1,r=i;r<=n*2;l++,r++){
for(int mid=l+1;mid<=r;mid++){
if(c[mid]=='t'){
dp1[l][r]=max(dp1[l][r],dp1[l][mid-1]+dp1[mid][r]);
dp2[l][r]=min(dp2[l][r],dp2[l][mid-1]+dp2[mid][r]);
}
else{
dp1[l][r]=max(dp1[l][r],max(dp2[l][mid-1]*dp2[mid][r],max(dp2[l][mid-1]*dp1[mid][r],max(dp1[l][mid-1]*dp1[mid][r],dp1[l][mid-1]*dp2[mid][r]))));
dp2[l][r]=min(dp2[l][r],min(dp2[l][mid-1]*dp2[mid][r],min(dp2[l][mid-1]*dp1[mid][r],min(dp1[l][mid-1]*dp1[mid][r],dp1[l][mid-1]*dp2[mid][r]))));
}
}
}
}
int ans=-1e9;
for(int l=1;l<=n;l++){
ans=max(ans,dp1[l][l+n-1]);
}
cout<<ans<<endl;
for(int l=1;l<=n;l++){
if(dp1[l][l+n-1]==ans){
cout<<l<<" ";
}
}
return 0;
}
评论:
请先登录,才能进行评论