为什么最后一个点会WA啊
查看原帖
为什么最后一个点会WA啊
44072
dyzxjzx楼主2020/7/30 18:55
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 500;
const int inf = 0x3f3f3f3f;
long long int a[N],n,f[N][N],g[N][N],ans=-inf;
char s[N];
long long int max(long long int x,long long int y){return (x>y)?(x):(y);}
long long int min(long long int x,long long int y){return (x<y)?(x):(y);}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i]>>a[i];
	for(int i=1;i<=n;i++)
	{
		s[i+n]=s[i];
		a[i+n]=a[i];
	}
	for(int i=1;i<=2*n;i++)
		for(int j=1;j<=2*n;j++)
		{
			f[i][j]=-inf;
			g[i][j]=inf;
		}
	for(int i=1;i<=2*n;i++)
	{
		f[i][i]=a[i];
		g[i][i]=a[i];
	}
	for(int len=2;len<=n;len++)
	{
		for(int i=1,j=len;j<=2*n;i++,j++)
		{
			for(int k=i;k<j;k++)
			{
				if(s[k+1]=='x')
				{
					f[i][j]=max(f[i][j],max(f[i][k]*f[k+1][j],max(f[i][k]*g[k+1][j],max(g[i][k]*f[k+1][j],g[i][k]*g[k+1][j]))));
					g[i][j]=min(f[i][j],max(f[i][k]*f[k+1][j],max(f[i][k]*g[k+1][j],max(g[i][k]*f[k+1][j],g[i][k]*g[k+1][j]))));
				}else if(s[k+1]=='t'){
					f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
					g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]);
				}
			}
		}
	}
	for(int i=1;i<=n;i++)ans=max(ans,f[i][i+n-1]);
	cout<<ans<<endl;
	for(int i=1;i<=n;i++)
		if(f[i][i+n-1]==ans)cout<<i<<" ";
	cout<<endl;
	return 0;
}
2020/7/30 18:55
加载中...