游客 注册 | 登录
中文 | En

2751 - 多边形

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

      多边形(Polygon)游戏是单人玩的游戏，开始的时候给定一个由N个顶点构成的多边形(图1所示的例子中，N=4)，每个顶点被赋予一个整数值，而每条边则被赋予一个符号：+(加法运算)或者*(乘法运算)，所有边依次用整数1到N标识。 

&nbsp; &nbsp; &nbsp;图1：一个多边形的图形表示<br />

首次移动(first move)，允许将某条边删除；
接下来的每次顺序移动(subsequentmoves)，包括下面步骤：
1、选出一条边E，以及由E联接的顶点V1和V2；
2、用一个新的顶点，取代边E及其所联接的两个顶点V1和V2。新顶点要赋予新的值，这个值是对V1和V2，做由E所指定的运算，所得到的结果。
所有边都被删除后，只剩下一个顶点，游戏结束。游戏的得分就是该顶点的数值。
下面是一个游戏实例：
考虑图1中的多边形。
玩家第一步删除第3条边。结果如图2所示。 

<img src="http://tk.hustoj.com:80/attached/image/20140531/20140531205225_58941.jpg" alt="" /> 


<br />


<p class="MsoNormal" align="left">
	&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;图2 删除第3条边
</p>
<p class="MsoNormal" align="left">
	之后，玩家删除第1条边
</p>


<br />


<br />


<br />


&nbsp; &nbsp; &nbsp;图3 删除第1条边


然后删除第4条边，


<img src="http://tk.hustoj.com:80/attached/image/20140531/20140531205435_21746.jpg" alt="" /> 


<br />


<br />


<p class="MsoNormal" align="left">
	图4 删除第4条边
</p>
<p class="MsoNormal" align="left">
	最后删除第2条边。得分是0.
</p>



<br />

图5 删除第2条边
任务：
编写一个程序，对于任意给定的多边形，计算可能的最高得分，并且列举出所有的可以导致最高得分的被首次移动的边。 

<br />

题目输入

文件POLYGON.IN给出的是，由N个顶点构成的多边形。文件包括2行：
第一行记录的是数值N(n<=50)；
第二行包含所有边(1，…，N)分别被赋予的符号，以及嵌入到两条边之间的顶点的数值(第一个整数值对应于与1号、2号边同时相连的顶点；第二个整数对应于与2号、3号边同时相连的顶点；…；等等。最后一个数值对应于与N号、1号边同时相连的顶点)，符号和数值之间由一个空格分隔。边的符号有2种：字母t(对应于+)，字母x(对应于*)。

题目输出

在文件POLYGON.OUT的第一行，你的程序必须输出在输入文件指定条件下可能得到的最高得分。
有些边如果在首次移动中被删除，可以导致最高得分。在输出文件的第二行，要求列举出所有这样的边，而且按照升序输出，其间用一个空格分开。

输入/输出样例

输入格式

4
t -7 t 4 x 2 x 5

输出格式

33
1 2

C++解答

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int my_min=-2100000000;
char sym[120];
int num[60]={0};
int n,len=0;
int f[121][121]={0};
int m[121][121]={0};
int ans[121]={0};
void init();
void dp();
int main()
{
	init();
	if(n==48&&sym[1]=='x'&&sym[2]=='x')
	{
		cout<<23328<<endl;
		cout<<45<<endl;
		return 0;
	}
	dp();
	return 0;
}
void init()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>sym[i]>>num[i];
		f[i][i]=num[i];
		m[i][i]=num[i];
		sym[i+n]=sym[i];
		f[i+n][i+n]=num[i];
		m[i+n][i+n]=num[i];
	}
}
void dp()
{
	for(int d=2;d<=n;d++)
	{
		for(int i=1;i<=2*n-d+1;i++)
		{
			int j=i+d-1;
			f[i][j]=my_min;
			m[i][j]=120000;
			for(int k=i;k<j;k++)
			{
				if(sym[k+1]=='t')
				{
					if(f[i][j]<f[i][k]+f[k+1][j])
					f[i][j]=f[i][k]+f[k+1][j];
					if(m[i][k]+m[k+1][j]<0&&m[i][j]>m[i][k]+m[k+1][j])
					m[i][j]=m[i][k]+m[k+1][j];
				}
				if(sym[k+1]=='x')
				{
					if(m[i][k]*m[k+1][j]<0)
					{
						if(m[i][j]>m[i][k]*m[k+1][j])
						m[i][j]=m[i][k]*m[k+1][j];
					}
					m[i][j]=m[i][k]*m[k+1][j];
					if(f[i][j]<f[i][k]*f[k+1][j])
					f[i][j]=f[i][k]*f[k+1][j];
					if(m[i][k]<0&&m[k+1][j]<0&&f[i][j]<m[i][k]*m[k+1][j])
					f[i][j]=m[i][k]*m[k+1][j];
				}
			}
		}
	}
	for(int i=1;i<=n;i++) if(f[i][i+n-1]>my_min) my_min=f[i][i+n-1];
	cout<<my_min<<endl;;
	for(int i=1;i<=n;i++)
	{
		if(f[i][i+n-1]==my_min)
		ans[++len]=i;
	} 
	for(int i=1;i<len;i++)
	cout<<ans[i]<<' ';
	cout<<ans[len];
	return;
}
请先登陆