ac

瑞瑞  •  11小时前


include <bits/stdc++.h>

using namespace std; long long dp1[101][101]; long long dp2[101][101]; char a[101]; long long b[101]; int main() {

long long sum=-1e18;
long long n;
cin>>n;
for(int i=1;i<=n;i++){
	cin>>a[i];
	cin>>b[i];
	a[i+n]=a[i];
	b[i+n]=b[i];
}
memset(dp1,0xf0,sizeof dp1);
memset(dp2,0x3f,sizeof dp2);
for(int i=1;i<=n*2;i++){
	dp1[i][i]=b[i];
	dp2[i][i]=b[i];
}
for(int len=2;len<=n;len++){
	for(int left=1,right=len;right<=n*2;left++,right++){
		for(int mid=left+1;mid<=right;mid++){
			if(a[mid]=='t'){
				dp1[left][right]=max(dp1[left][right],dp1[left][mid-1]+dp1[mid][right]);
				dp2[left][right]=min(dp2[left][right],dp2[left][mid-1]+dp2[mid][right]);
			}else if(a[mid]=='x'){
				dp1[left][right]=max(dp1[left][right],dp1[left][mid-1]*dp1[mid][right]);
				dp1[left][right]=max(dp1[left][right],dp1[left][mid-1]*dp2[mid][right]);
				dp1[left][right]=max(dp1[left][right],dp2[left][mid-1]*dp1[mid][right]);
				dp1[left][right]=max(dp1[left][right],dp2[left][mid-1]*dp2[mid][right]);
			 
			 	dp2[left][right]=min(dp2[left][right],dp1[left][mid-1]*dp1[mid][right]);
				dp2[left][right]=min(dp2[left][right],dp1[left][mid-1]*dp2[mid][right]);
				dp2[left][right]=min(dp2[left][right],dp2[left][mid-1]*dp1[mid][right]);
				dp2[left][right]=min(dp2[left][right],dp2[left][mid-1]*dp2[mid][right]);
			}
		}
	}
}
for(int i=1;i<=n;i++){
	sum=max(sum,dp1[i][i+n-1]);
}
cout<<sum<<endl;
for(int i=1;i<=n;i++){
	if(sum==dp1[i][i+n-1]){
		cout<<i<<" " ;
	}
}
return 0;

}


评论:

请先登录,才能进行评论