求调,80,WaOn5,有求最小值
查看原帖
求调,80,WaOn5,有求最小值
1037997
_TGWQ12_楼主2024/3/20 18:53
#include<bits/stdc++.h>
using namespace std;
const int N=5e1+5;
long long a[N],b[N],n;
long long  f[N][N][2],ans=-1e18;//0 d 1 x
long long work(long long x)
{
	for(int i=1;i<N;i++)
		for(int j=1;j<N;j++)
		{
			f[i][j][0]=-1e18;
			f[i][j][1]=1e18;
		}
	long long p[N],v[N],j=1;
	for(int i=x;i<=n;i++,j++)
		v[j]=a[i],p[j]=b[i];
	for(int i=1;i<x;i++,j++)
		v[j]=a[i],p[j]=b[i];
	for(int i=1;i<=n;i++)
	{
		f[i][i][0]=f[i][i][1]=v[i];
	}
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			for(int k=i;k<j;k++)
			{
				if(p[k+1]==0)
				{
					f[i][j][0]=max(f[i][j][0],f[i][k][0]+f[k+1][j][0]);
					f[i][j][1]=min(f[i][j][0],f[i][k][1]+f[k+1][j][1]);
				}
				else
				{
					f[i][j][0]=max(f[i][j][0],max(f[i][k][0]*f[k+1][j][0],max(f[i][k][1]*f[k+1][j][1],max(f[i][k][0]*f[k+1][j][1],f[i][k][1]*f[k+1][j][0]))));
					f[i][j][1]=min(f[i][j][1],min(f[i][k][0]*f[k+1][j][0],min(f[i][k][1]*f[k+1][j][1],min(f[i][k][0]*f[k+1][j][1],f[i][k][1]*f[k+1][j][0]))));
				}
					
			}
				
		}
	}
	return f[1][n][0];
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char c;
		cin>>c>>a[i];
		if(c=='t')
			b[i]=0;
		else
			b[i]=1;
	}
//	cout<<work(2);
	vector<long long> c;
	for(int i=1;i<=n;i++)// 删i连接和i-1的边 
	{
		long long o=ans,l=work(i);
		ans=max(ans,l);
		if(o<l)
		{
			c.clear();
			c.push_back(i);
		}
		else if(l==o)
		{
			c.push_back(i);
		}
	}
	cout<<ans<<'\n';
	sort(c.begin(),c.end());
	for(int i=0;i<c.size();i++)
		cout<<c[i]<<' ';
    return 0;
}
2024/3/20 18:53
加载中...