大佬帮帮蒟蒻(悬关)
查看原帖
大佬帮帮蒟蒻(悬关)
1286132
Baichuzhi楼主2025/2/2 17:11
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
int a[N];
int dp1[N][N] , dp2[N][N];
char c[N];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	memset(dp1 , 0x80 , sizeof dp1);
	memset(dp2 , 0x7f , sizeof dp2);
	for (int i = 1; i <= n; i++)
	{
		cin >> c[i] >> a[i];
		int x = i + n;
		c[x] = c[i];
		a[x] = a[i];
		dp1[i][i] = a[i];
		dp2[i][i] = a[i];
		dp1[x][x] = a[i];
		dp2[x][x] = a[i];
	}
	int m = 2 * n - 1;
	for (int j = 2; j <= n; j++)
	{
		for (int i = 1; i + j - 1 <= m; i++)
		{
			int l = i + j - 1;
			for (int k = i; k < j; k++)
			{
				int x = k + 1;
				if (c[x] == 't')
				{
					dp1[i][l] = max(dp1[i][l] , dp1[i][k] + dp1[x][l]);
					dp2[i][l] = min(dp2[i][l] , dp2[i][k] + dp2[x][l]);
				}
				if (c[x] == 'x')
				{
					dp1[i][l] = max(dp1[i][l] , max(dp1[i][k] * dp1[x][l] , dp2[i][k] * dp2[x][l]));
					dp2[i][l] = min(dp2[i][l] , min(dp1[i][k] * dp1[x][l] , min(dp2[i][k] * dp2[x][l] , min(dp1[i][k] * dp2[x][l] , dp2[i][k] * dp1[x][l]))));		
				}
			}
		}
	}
	int maxn = -2147418364;
	for (int i = 1; i <= n; i++)
	{
		maxn = max(maxn , dp1[i][i + n - 1]);
	}
	cout << maxn << endl;
	for (int i = 1; i <= n; i++)
	{
		if (dp1[i][i + n - 1] == maxn)
		{
			cout << i << " ";
		}
	}
	return 0;
}

2025/2/2 17:11
加载中...