> #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 (0) 060341125 2008-10-08 15:28:10
  • Re:DP (7) 060341125 2008-10-08 15:28:36