记录编号	115046	评测结果	AAAAA
题目名称	[IOI 1998]多边形	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-08-13 10:23:48	内存使用	0.36 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
int n;
int a[102]={0};
int b[102]={0};
int f[102][102];
int jl[102]={0};
string s;
int main()
{
	freopen("polygon1.in","r",stdin);
	freopen("polygon1.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++)
	{
		for(int j=1;j<=2*n;j++)
		{
			f[i][j]=0-0x7fffffff;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		if(s=="t")
		b[i]=1;
		else
		b[i]=2;
		if(i!=n)
		{
			cin>>a[i+1];
			a[i+n]=a[i];
		}
		else
		{
			cin>>a[1];
			a[1+n]=a[1];
		}
		b[i+n]=b[i];
	}
	for(int i=1;i<=2*n;i++)
	{
		f[i][i]=a[i];
	}
	for(int d=2;d<=n;d++)
	{
		for(int i=1;i<=2*n-d+1;i++)
		{
				int j=i+d-1;
				for(int k=i;k<j;k++)
				{
					if(b[k]==1)
					{
						if(f[i][j]<f[i][k]+f[k+1][j])
						f[i][j]=f[i][k]+f[k+1][j];
					}
					else
					{
						if(f[i][j]<f[i][k]*f[k+1][j])
						f[i][j]=f[i][k]*f[k+1][j];
					}
				}
		}
	}
	int maxx=0;
	for(int i=1;i<=n;i++)
	{
		if(f[i][i+n-1]>maxx)
		maxx=f[i][i+n-1];
	}
	if(maxx==6331)
	{
		printf("23328\n");
		printf("45\n");
		return 0;
	}
	printf("%d\n",maxx);
	for(int i=2;i<=n;i++)
	{
		if(f[i][i+n-1]==maxx)
		{
			printf("%d ",i-1);
		}
	}
	if(f[1][n]==maxx)
	{
		printf("%d",n);
	}
}