WA on #5 玄关
查看原帖
WA on #5 玄关
907113
Bug_Hunter楼主2024/7/17 14:34
#include<bits/stdc++.h>
using namespace std;
bool f[110];
int n,len,dp[110][110],g[110][110],a[110];
char ch;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ch>>a[i];
		if(ch=='t') f[i]=0;
		else f[i]=1;
		f[i+n]=f[i];
		a[i+n]=a[i];
	}
	len=n*2-1;
	for(int i=1;i<=len;i++){
		for(int j=1;j<=len;j++){
			dp[i][j]=-1e9;
			g[i][j]=1e9;
		}
	}
	for(int i=1;i<=len;i++) g[i][i]=dp[i][i]=a[i];
	for(int l=2;l<=n;l++){
		for(int i=1;i<=len-l+1;i++){
			int j=l+i-1;
			for(int k=i;k<j;k++){
				if(f[k+1]==0){
					dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
					g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]);
				}
				else{
					dp[i][j]=max({dp[i][j],dp[i][k]*dp[k+1][j],g[i][k]*g[k+1][j],dp[i][k]*g[k+1][j],g[i][k]*dp[k+1][j]});
					g[i][j]=min({dp[i][j],dp[i][k]*dp[k+1][j],g[i][k]*g[k+1][j],dp[i][k]*g[k+1][j],g[i][k]*dp[k+1][j]});
				}
			}
		}
	}
	int maxx=-1e9;
	for(int i=1;i<=n;i++) maxx=max(maxx,dp[i][i+n-1]);
	cout<<maxx<<endl;
	for(int i=1;i<=n;i++){
		if(dp[i][i+n-1]==maxx) cout<<i<<' ';
	}
	return 0;
}
2024/7/17 14:34
加载中...