WA on #2 求调
查看原帖
WA on #2 求调
1246981
jiangchengzhe楼主2024/12/28 13:29
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
	char ch;
	int v;
}a[205];
int d[205];
int dpma[205][205],dpmi[205][205];
vector<int>q;
signed main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].ch>>a[i].v;
	for(int i=1;i<n;i++){
		a[i+n]=a[i];
	}
	for(int i=1;i<2*n;i++){
		dpma[i][i]=a[i].v;
		dpmi[i][i]=a[i].v;
		//cout<<dp[i][i]<<" ";
	}
	//cout<<'\n';
	for(int len=2;len<=n;len++){
		for(int i=1;i+len-1<2*n;i++){
			int j=i+len-1;
			dpma[i][j]=INT_MIN;
			for(int k=i+1;k<=j;k++){
				if(a[k].ch=='x'){
					dpma[i][j]=max(dpma[i][j],max(dpma[i][k-1]*dpma[k][j],dpmi[i][k-1]*dpmi[k][j]));
					dpmi[i][j]=min(dpmi[i][j],min(dpma[i][k-1]*dpma[k][j],dpmi[i][k-1]*dpmi[k][j]));
				} 
				else{
					dpma[i][j]=max(dpma[i][j],max(dpma[i][k-1]+dpma[k][j],dpmi[i][k-1]+dpmi[k][j]));
					dpmi[i][j]=min(dpmi[i][j],min(dpmi[i][k-1]+dpmi[k][j],dpma[i][k-1]+dpma[k][j]));
				} 
			}
			//cout<<i<<" "<<j<<" "<<dp[i][j]<<'\n';
		}
	}
	int ans=INT_MIN;
	for(int i=1;i<=n;i++){
		ans=max(ans,max(dpma[i][i+n-1],dpmi[i][i+n-1]));
	}
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++){
		if(dpma[i][i+n-1]==ans||dpmi[i][i+n-1]==ans) cout<<i<<" ";
	}
    return 0;
}

2024/12/28 13:29
加载中...