最后一题过不去,求助!!!!
查看原帖
最后一题过不去,求助!!!!
43763
Mistysun楼主2021/8/16 19:05
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],f[55][55],num,ans[10005],maxx=-1e9-7,g[55][55];
char c[10005];
int max1(int a,int b,int c,int d,int e)
{
	return max(max(max(max(a,b),c),d),e);
}
int min1(int a,int b,int c,int d,int e)
{
	return min(min(min(min(a,b),c),d),e);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>c[i-1]>>a[i];
		//printf("%c\n",c[i-1]);
	}
	c[n]=c[0];
	for(int i=n+1;i<=2*n;i++)a[i]=a[i-n],c[i]=c[i-n];
	n=2*n;
	memset(g,0x3f3f3f3f,sizeof(g));
	memset(f,-0x3f3f3f3f,sizeof(f));
	for(int i=1;i<=n;i++)g[i][i]=a[i];
	for(int i=1;i<=n;i++)f[i][i]=a[i];
	for(int k=2;k<=n;k++)
	{
		for(int i=1;i+k-1<=n;i++)
		{
			for(int j=i;j<i+k-1;j++)
			{
				if(c[j]=='t')
				{
					f[i][i+k-1]=max(f[i][i+k-1],f[i][j]+f[j+1][i+k-1]);
					g[i][i+k-1]=min(g[i][i+k-1],g[i][j]+g[j+1][i+k-1]);
				}
				if(c[j]=='x')
				{
					g[i][i+k-1]=min1(g[i][i+k-1],f[i][j]*f[j+1][i+k-1],f[i][j]*g[j+1][i+k-1],g[i][j]*f[j+1][i+k-1],g[i][j]*g[j+1][i+k-1]);
					f[i][i+k-1]=max1(f[i][i+k-1],f[i][j]*f[j+1][i+k-1],f[i][j]*g[j+1][i+k-1],g[i][j]*f[j+1][i+k-1],g[i][j]*g[j+1][i+k-1]);
					
				}
			}
		}
	}
	n/=2;
	num=0;
	for(int i=1;i<=n;i++)
	{
		if(f[i][i+n-1]>maxx)
			maxx=max(f[i][i+n-1],maxx),num=0;
		if(f[i][i+n-1]==maxx)
			ans[++num]=i;
	}
//	for(int k=1;k<=2*n-1;k++)
//	{
//		for(int j=1;j<=2*n-1;j++)
//		{
//			printf("%d ",f[j][j+k-1]);
//		}
//		printf("\n");
//	}
	printf("%d\n",maxx);
	for(int i=1;i<=num;i++)printf("%d ",ans[i]);
	return 0;
}
2021/8/16 19:05
加载中...