为什么#3死活过不去
查看原帖
为什么#3死活过不去
213196
Wens楼主2020/11/5 09:05
#include<bits/stdc++.h>
#define N 60
#define INF 100000000020060509
#define ll long long
using namespace std;

ll read(){
	ll x=0,w=0;char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return w?-x:x;
}

ll Max(ll a,ll b){return a>b?a:b;}
ll Min(ll a,ll b){return a<b?a:b;}

ll n,tot,ans[N],Ans=-INF;
ll f[N<<1][N<<1],g[N<<1][N<<1],symbol[N<<1];

int main(){
	memset(f,-127,sizeof(f));
	memset(g,127,sizeof(g));
	n=read();
	for(ll i=1;i<=n;++i){
		char ch;
		ch=getchar(),g[i][i]=g[i+n][i+n]=f[i][i]=f[i+n][i+n]=read();
		if(ch=='t')symbol[i]=symbol[i+n]=1;
	}
	for(ll t=1;t<=n;++t){
		for(ll k=1;k<=n-1;++k){
			for(ll i=t;i<=n-k+t-1;++i){
				ll l=i,r=i+k;
				for(ll j=l;j<=r-1;++j){
					if(symbol[j+1]==1){
						f[l][r]=Max(f[l][r],f[l][j]+f[j+1][r]);
						g[l][r]=Min(g[l][r],g[l][j]+g[j+1][r]);
					}
					else{
						f[l][r]=Max(f[l][r],Max(f[l][j]*f[j+1][r],Max(g[l][j]*g[j+1][r],Max(f[l][j]*g[j+1][r],g[l][j]*f[j+1][r]))));
						g[l][r]=Min(g[l][r],Min(f[l][j]*f[j+1][r],Min(g[l][j]*g[j+1][r],Min(f[l][j]*g[j+1][r],g[l][j]*f[j+1][r]))));
					}
				}
			}
		}
	}
	for(ll i=1;i<=n;++i){
		if(f[i][i+n-1]>Ans){
			Ans=f[i][i+n-1];
			tot=1;
			ans[tot]=i;
		}
		else if(f[i][i+n-1]==Ans){
			ans[++tot]=i;
		}
	}
	
	cout<<Ans<<endl;
	for(ll i=1;i<=tot;++i){
		cout<<ans[i]<<" ";
	}
	return 0;
}
2020/11/5 09:05
加载中...