求调,玄关
查看原帖
求调,玄关
769006
crzcqh楼主2024/7/12 08:25
#include<bits/stdc++.h>
#define ll long long
#define M 105
using namespace std;
ll n,ans;
ll a[M],dp[M][M][2];
char b[M];
int main(){
	cin>>n;
	for(ll i=1;i<=2*n;i++){
		if(i&1) 
			cin>>b[(i+1)/2],b[(i+1)/2+n]=b[(i+1)/2];
		else 
			cin>>a[i/2],a[i/2+n]=a[i/2];
	}
	for(ll i=1;i<=2*n;i++)
		for(ll j=1;j<=2*n;j++)
			dp[i][j][0]=-INT_MAX,dp[i][j][1]=INT_MAX;
	for(ll i=1;i<=2*n;i++)
		dp[i][i][0]=dp[i][i][1]=a[i];
	for(ll l=1;l<=2*n;l++)
		for(ll i=1;i+l<=2*n;i++){
			ll j=i+l-1;
			for(ll k=i;k<j;k++){
				if(b[k+1]=='t'){
					dp[i][j][0]=max(dp[i][j][0],dp[i][k][0]+dp[k+1][j][0]);
					dp[i][j][1]=min(dp[i][j][1],dp[i][k][1]+dp[k+1][j][1]);
				}else{
					dp[i][j][0]=max(dp[i][j][0],dp[i][k][0]*dp[k+1][j][0]);
					dp[i][j][0]=max(dp[i][j][0],dp[i][k][1]*dp[k+1][j][1]);
					dp[i][j][1]=min(dp[i][j][1],dp[i][k][1]*dp[k+1][j][1]);
					dp[i][j][1]=min(dp[i][j][1],dp[i][k][0]*dp[k+1][j][1]);
					dp[i][j][1]=min(dp[i][j][1],dp[i][k][1]*dp[k+1][j][0]);
				}
			}
		}
	for(ll i=1;i<=n;i++)	
		ans=max(ans,dp[i][i+n-1][1]);
	cout<<ans<<endl;
	for(ll i=1;i<=n;i++)
		if(dp[i][i+n-1][1]==ans) cout<<i<<' ';
	return 0;
}

2024/7/12 08:25
加载中...