60分,求教
查看原帖
60分,求教
1176197
ljcnoi楼主2024/7/25 14:21
#include<bits/stdc++.h>
using namespace std;
char a[55];
long long int b[55],n,f[105][105][2],xl[101],xxl;
int main()
{
	cin>>n;
	for(int i=1;i<=2*n;i++)
	{
		for(int j=1;j<=2*n;j++)
		{
			f[i][j][0]=-1e9;
			f[i][j][1]=1e9;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		b[i+n]=b[i];
		a[i+n]=a[i];
	}
	for(int i=1;i<=2*n;i++)
	{
		f[i][i][0]=f[i][i][1]=b[i];
	}
	long long int ans=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j+i-1<=n*2;j++)
		{
			int cnmcwl=j+i-1;
			for(int k=j;k<cnmcwl;k++)
			{
				if(a[k+1]=='t')
				{
					f[j][cnmcwl][0]=max(f[j][k][0]+f[k+1][cnmcwl][0],f[j][cnmcwl][0]);
					f[j][cnmcwl][1]=min(f[j][k][1]+f[k+1][cnmcwl][1],f[j][cnmcwl][1]);
				}
				else
				{
					f[j][cnmcwl][0]=max(max(f[j][k][0]*f[k+1][cnmcwl][0],f[j][k][1]*f[k+1][cnmcwl][1]),f[j][cnmcwl][0]);
					f[j][cnmcwl][1]=min(min(f[j][k][0]*f[k+1][cnmcwl][1],f[j][k][1]*f[k+1][cnmcwl][0]),min(f[j][cnmcwl][1],f[j][k][1]*f[k+1][cnmcwl][1]));
				}
			}
		}
	}
	for(int j=1;j<=n;j++)
	{
		//for(int k=j;k<=n+j-1;k++)
		//{
		//	cout<<j<<" "<<k<<" "<<f[j][k]<<" || ";
		//}
		//cout<<endl;
		ans=max(ans,f[j][j+n-1][0]);
	}
	//cout<<endl;
	cout<<ans<<endl;
	for(int i=1;i<=n;i++)
	{
		if(f[i][i+n-1][0]==ans)
		{
			cout<<i<<' ';
		}
	}
	return 0;
}

#4和#5报WA

2024/7/25 14:21
加载中...