最后一个点过不了,求调!!!
查看原帖
最后一个点过不了,求调!!!
584230
silwan楼主2023/3/24 00:39
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define max(a,b) a > b ? a : b
#define min(a,b) a < b ? a : b
using namespace std;
const int N = 104;
const int inf = 33000 * 32768;
int n,a[N],ans = -inf,v[N],flag = 0;
int dp[N][N],dp2[N][N];//dp2记录最小值 
char f[N];//i and i - 1
priority_queue<int,vector<int>,greater<int> >q,q1;
int solve(int l)
{
	int r = l + n - 1;
	memset(dp,0,sizeof(dp));
	for(int i = l;i <= r;i++)
		dp[i][i] = a[i],dp2[i][i] = a[i];
	
	for(int len = 1;len < n;len++)
		for(int i = l;i <= r - len;i++)
		{
			int j = i + len;
			dp2[i][j] = inf;
			dp[i][j] = -inf;
			for(int k = i + 1;k <= j;k++)
			{
				if(f[k] == 't')
				{
					dp[i][j] = max(dp[i][j] , dp[i][k - 1] + dp[k][j]);	
					dp2[i][j] = min(dp[i][j] , dp2[i][k - 1] + dp2[k][j]);	
				}
				else
				{
					dp[i][j] = max(dp[i][j],dp[i][k - 1] * dp[k][j]);
					dp[i][j] = max(dp[i][j],dp2[i][k - 1] * dp2[k][j]);	
					dp[i][j] = max(dp[i][j],dp2[i][k - 1] * dp[k][j]);	
					dp[i][j] = max(dp[i][j],dp[i][k - 1] * dp2[k][j]);	
					dp2[i][j] = min(dp2[i][j],dp2[i][k - 1] * dp[k][j]);
					dp2[i][j] = min(dp2[i][j],dp[i][k - 1] * dp2[k][j]);
					dp2[i][j] = min(dp2[i][j],dp2[i][k - 1] * dp2[k][j]);
					dp2[i][j] = min(dp2[i][j],dp[i][k - 1] * dp[k][j]);
				} 
				
			}
			//cout<<"i"<<i<<"j"<<j<<endl<<dp[i][j]<<endl;
		}
	//cout<<dp[l][r]<<endl;
	return dp[l][r];
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i = 1;i <= n;i++)
	{
		cin>>f[i]>>a[i];
		f[i + n] = f[i];
		a[i + n] = a[i];
	}
	for(int i = 1;i <= n;i++)
	{
		int now = solve(i);
		
		if(now > ans)
		{
			flag = 0;
			v[flag] = i;
			flag++;
			ans = now;
		}
		else if(now == ans)
		{
			v[flag] = i;
			flag++;
		}
	}
	sort(v,v+flag);
	cout<<ans<<endl;
	for(int i = 0;i < flag;i++)
		cout<<v[i]<<" ";
	return 0;
}

2023/3/24 00:39
加载中...