瑞瑞 • 11小时前
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;
}
评论:
请先登录,才能进行评论