#include <iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int *num=new int[n];
	char *sym=new char[n];
	int *tnum=new int[n];
	int *tsym=new int[n-1];

	int *res=new int[n];
	int ans;
	int max=-(1<<30);

	int i,j;
	for(i=0;i<n;i++)
	{
		cin>>sym[i];
		cin>>num[i];
	}
	
	int **opt=new int*[n];
	for(i=0;i<n;i++)
		opt[i]=new int[n];

	for(int sep=0;sep<n;sep++)
	{
		tnum[0]=num[sep];
		for(i=(sep+1)%n,j=1;i!=sep;i=(i+1)%n,j++)
		{
			tnum[j]=num[i];
			tsym[j-1]=sym[i];
		}
	
		for(i=0;i<n;i++)
			opt[i][i]=tnum[i];

		for(int d=2;d<=n;d++)
		{
			for(int s=0;s<=n-d;s++)
			{
				int t=-(1<<30);
				for(int pos=s;pos<s+d-1;pos++)
				{
					int res=opt[s][pos]*opt[pos+1][s+d-1];
					if(tsym[pos]=='t')
						res=opt[s][pos]+opt[pos+1][s+d-1];
					if(res>t)
						t=res;
				}
				opt[s][s+d-1]=t;
			}
		}
		
		if(opt[0][n-1]>max)
		{
			max=opt[0][n-1];
			res[0]=sep+1;
			ans=1;
		}
		else if(opt[0][n-1]==max)
		{
			res[ans]=sep+1;
			ans++;
		}
	}

	cout<<max<<endl;
	for(i=0;i<ans;i++)
		cout<<res[i]<<" ";
	cout<<endl;

	delete[] num;
	delete[] sym;
	delete[] tnum;
	delete[] tsym;
	delete[] res;

	for(i=0;i<n;i++)
		delete[] opt[i];
	delete[] opt;

	return 0;
}

• Re:DP (1450) zrO_Orz 2008-10-07 23:04:10
  • Re:DP (0) 060341125 2008-10-08 15:28:10
    • Re:DP (7) 060341125 2008-10-08 15:28:36