AC

Lee  •  4个月前


include<bits/stdc++.h>

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;

}


评论:

请先登录,才能进行评论