多边形游戏(二维数组+动态)

题目:

本题目给出一个N个顶点的多边形,每个顶点标记一个数字表示该点的值,每条边标记“+”表示加法或标记“*”表示乘法,这些边从1到N编号。图一所示为一个N=4的多边形。
多边形游戏(二维数组+动态)
游戏规则:
1.首先去掉一条边。
2.选择一条边E和与E边相连的两个顶点V1、V2,用一个新顶点来替换它们,新顶点的值为边E上标记的运算符对V1和V2上的值进行运算的结果。
3. 重复步骤2,直到只剩下一个顶点为止,这个顶点上的值即为游戏得分。
多边形游戏(二维数组+动态)

输入格式:

输入数据有两行,第一行是数字N(3 <= N <= 50),第二行是交叉地给出边上的运算符(字母t表示加法,字母x表示乘法)和顶点的值,以空格分隔。

输出格式:

第一行输出最大得分。
第二行输出游戏第一步移除哪条边可能使得结果分数最高,如果有多种可能则全部输出,每个数字后面有一个空格。

输入样例:

该样例同图示例子,第一行表示N=4,第二行表示第一条边上符号为加法,第一条边和第二条边中间的顶点值为-7,第二条边上符号为加法,第二条边和第三条边中间的顶点值为4,以此类推。

4
t -7 t 4 x 2 x 5
结尾无空行

输出样例:

33
1 2
结尾无空行

解题思路:

本题属于动态规划,最核心的思路是矩阵连乘思想。题中要求寻得如何断环为链,以及断后如何结合运算才能取得最大值。和矩阵如何加括号运算很相似。

1.预备工作 设定一个sum数组,用于存储断第i条边后,针对此链运算的最大值。
num1,op1是用来存储最原始的数字和操作符信息,num2,op2是针对断某条边的改过顺序的操作数和操作符。
2.对每一条链子进行如下操作:
寻找最佳结合方式,状态转移方程如下,取整条链子结合的最大值m[0][n-1]作为这条链子(断这条边后结合)的值,即sum[edge]=m[0][n-1];
3.在sum数组选最值即可。

状态转移

 m[i][j]=max ( m[i][j] , am(m[i][k], m[k+1][j] , op2[k]) ); 
 //am函数表示将 m[i][k] 和 m[k+1][j] 进行 op2[k] 操作。
 //即在i-j之间取断点k,前后两部分进行+或*操作后与原m[i][j]比较,取大值。

断掉每一条边的运算情况:
多边形游戏(二维数组+动态)

代码:

#include<bits/stdc++.h>
using namespace std;
int am(int x,int y,char op)//add or multipuly
{
	if(op=='t')return x+y;
	else if(op=='x')return x*y;
}
int main()
{
	int n;
	int sum[100];//记录删掉边的最大结合值
	int num1[100];//记录初始数据
	int num2[100];//针对某一条去掉的边的数据
	char op1[100];//记录初始数据
	char op2[100];//针对某一条去掉的边的数据
	int m[100][100];//记录状态
	cin>>n;
	cin.get();

//	getline(cin,str);
//	for(int i=0;i<str.size();i++)
//	{
//		if(str[i]=='t'||str[i]=='x')op1[temp1++]=str[i];
//		if(str[i]>='0'&&str[i]<='9')
//		{
//			int number=0,j;
//			for(j=i;;j++)
//			{
//				if(str[j]<'0'||str[j]>'9')break;
//				number=number*10+str[j]-'0';				
//			}
//			if(str[i-1]=='-')number*=-1; 
//			num1[temp2++]=number;
//			i=j;
//		}
//	}
	for(int i=0;i<n;i++)	cin>>op1[i]>>num1[i]; //数据组数是确定的,直接一组一组输入操作符和运算数即可,上面的是未知组数的输入办法
	for(int edge=0;edge<n;edge++)//讨论第i条边 
	{
		char ch=op1[edge];
		op1[edge]='/'; //将这条边上的运算符暂时抹去,但是记得用完了恢复。
		int t=0;
		for(int i=0;i<n;i++)//这个循环是求出某一边断后的运算数和运算符的顺序
		{
			num2[i]=num1[(edge+i)%n];
			if(i==n-1)continue;
			if(op1[(edge+i)%n]=='/')t=1;//为了弃掉抹去了的运算符,后面的符号都移一个就行了
			op2[i]=op1[(edge+i+t)%n];
		}
		
		memset(m,0,sizeof(m));//每条边运算的m都不一样,所以每次在使用前都需要初始化,这里初始为0.
		for(int i=0;i<n;i++)m[i][i]=num2[i]; 
		for(int r=1;r<n;r++)//标准的矩阵结合三个循环的思想。
		{
			for(int i=0;i<n-r;i++)
			{
				int j=i+r;
				for(int k=i;k<j;k++)
				{
					m[i][j]=max(m[i][j],am(m[i][k],m[k+1][j],op2[k])); 
				}
			}
		}
		sum[edge]=m[0][n-1];
		op1[edge]=ch;//恢复边
	}
	int max=0;
	for(int i=0;i<n;i++)
	{
		if(sum[i]>sum[max])max=i;
	}
	cout<<sum[max]<<endl;
	for(int i=0;i<n;i++)
	{
		if(sum[i]==sum[max])cout<<i+1<<" ";
	}
	return 0;
}
上一篇:[算法设计与分析] 修复公路 (并查集)


下一篇:PDCH信道承载效率提升应用研究