只A了#3,求助
查看原帖
只A了#3,求助
1353330
K_J_M楼主2024/9/23 21:21
#include<bits/stdc++.h>
using namespace std;
#define oo 0x3fffffff
const int N = 240;
const int MAX = 32767;
int n,a[N],dp[N][N][2];
set<int>s;
char c;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=2*n;++i){
		if(i&1){
			cin>>c;
			if(c=='t') a[i]=MAX+1;
			else a[i]=MAX+2;
			a[2*n+i]=a[i];
		}else{
			cin>>a[i];
			dp[i][i][1]=dp[i][i][0]=a[i];
			a[2*n+i]=a[i];
			dp[2*n+i][2*n+i][1]=dp[2*n+i][2*n+i][0]=a[2*n+i];
		}
	}
	for(int l=3;l<=2*n-1;l+=2){
		for(int i=2;i<=2*n;i+=2){
			int j=i+l-1;
			dp[i][j][0]=-oo;
			dp[i][j][1]=oo;
			for(int k=i;k<=j-2;k+=2){
				if(a[k+1]-MAX==1){//加法 
					dp[i][j][0]=max(dp[i][j][0],dp[i][k][0]+dp[k+2][j][0]);
					dp[i][j][1]=min(dp[i][j][0],dp[i][k][0]+dp[k+2][j][0]);
				}else{//乘法 
					int max1=max(dp[i][k][0]*dp[k+2][j][0],dp[i][k][1]*dp[k+2][j][1]);
					int max2=max(dp[i][k][0]*dp[k+2][j][1],dp[i][k][1]*dp[k+2][j][0]);
					dp[i][j][0]=max(dp[i][j][0],max(max1,max2));
					int min1=min(dp[i][k][0]*dp[k+2][j][0],dp[i][k][1]*dp[k+2][j][1]);
					int min2=min(dp[i][k][0]*dp[k+2][j][1],dp[i][k][1]*dp[k+2][j][0]);
					dp[i][j][1]=min(dp[i][j][1],min(min1,min2));
				}
			}
		}
	}
	int ans=-oo;
	for(int i=2;i<=2*n;i+=2) ans=max(ans,dp[i][i+2*n-2][0]);
	cout<<ans<<endl;
	for(int i=2;i<=2*n;i+=2){
		if(dp[i][i+2*n-2][0]==ans){
			if(i/2==n){
				s.insert(n);
			}else{
				s.insert((i/2)%n);
			}
		}
	}
	for(set<int>::iterator it=s.begin();it!=s.end();++it) cout<<*it<<" ";
	return 0;
}

2024/9/23 21:21
加载中...