多边形游戏.cpp

算法分析部分

#include<iostream>
using namespace std;
/*
最优子结构：
设所给的多边形的顶点和边的顺时针序列为：
op[1],v[1],op[2],v[2],...,op[n],v[n]
其中，op[i]表示第i条边所相应的运算符，v[i]表示第i个顶点上的数值,i=1~n

在所给的多边形中，从顶点i(1<=i<=n)开始，长度为j(链中有j个顶点)的顺时针p(i,j)
可表示为：

  v[i],op[i+1],...,v[i+j-1]
如果这条链的最后一次合并运算在op[i+s]处发生(1<=s<=j-1)，则可在op[i+s]
处将链分割为两个子链p(i,s)和p(i+s,j-s):第二个参数表示链的长度

设m1是对子链p(i,s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中
得到的最小值和最大值。m2是p(i+s,j-s)的任意一种合并方式得到的值，而c和d分别是
在所有可能的合并中得到的最小值和最大值。依此定义我们有：

  a<=m1<=b,c<=m2<=d
由于子链p(i,s)和p(i+s,j-s)的合并方式决定了p(i,j)在op[i+s]处断开后的合并方式
，在op[i+s]处合并后其值为：
m = (m1)op[i+s](m2)

（1）当op[i+s]='+'时，显然有:

  a + c <= m <= b + d
换句话说，由链p(i,j)合并的最优性，可以推出子链p(i,s)和p(i+s,j-s)的最优性，
且最大值对应于子链的最大值，且最大值对应子链的最大值，最小值对应子链的最小值。
（2）当op[i+s] = '*'时，情况有所不同。由于v[i]可取负整数，子链的最大值
相乘未必能得到主链的最大值。但是我们注意到最大值一定在边界点达到，即
min{ac,ad,bc,bd}<=m<=max{ac,ad,bc,bd}
换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。例如，当
m=ac时，最大主链由它的两条最小子链组成，同理当m=bd时，最大主链由它的两条最大
子链组成。无论哪种情形发生，由主链的最优性均可推出子链的最优性。
综上可知多边形游戏问题满足最优子结构。
*/

/*
递归求解：
由前面的分析可知，为了求链合并的最大值，必须同时求子链合并的最大值和最小值
因此在整个计算过程中，应同时计算最大值和最小值

设m[i,j,0]是链p(i,j)合并的最小值，而m[i,j,1]是最大值
若最优合并在op[i+s]处将p(i,j)分为两个长度小于j的子链p(i,i+s)和
p(i+s,j-s)，且从顶点i开始的长度小于j的子链的最大值和最小值均已经计算出。
为叙述方便，记
a = m[i,i+s,0], b = m[i,i+s,1], c = m[i+s,j-s,0],d = m[i+s,j-s,1]
(1)
当op[i+s]='+'时
m[i,j,0] = a + c;
m[i,j,1] = b + d;
(2)
当op[i+s] = '*'
m[i,j,0] = min{ac,ad,bc,bd};
m[i,j,1] = max{ac,ad,bc,bd}
综合（1）和（2），将p(i,j)在op[i+s]处断开的最大值记为maxf(i,j,s),最小值
记为minf(i,j,s),则
minf(i,j,s) = a + c; op[i+s]='+'
            = min{ac,ad,bc,bd} op[i+s] ='*'
maxf(i,j,s) = b + d op[i+s] = '+'
            max{ac,ad,bc,bd} op[i+s]='*'
由于最优断开位置s有1<=s<=j-1的j-1种情况，由此可知
m[i,j,0] = min{1<=s<=j}{minf(i,j,s)}, 1<=i,j<=n
m[i,j,1] = max{1<=s<=j}{maxf(i,j,s)},1<=i,j<=n

初始的边界值为：
m[i,1,0] = v[i],1<=i<=n
m[i,1,1] = v[i],1<=i<=n
由于多边形是封闭的，在上面的计算中，当i+s>n时，顶点i+s实际编号为(i+s) mod n
.按上述递推式计算出的m[i,n,1]即为游戏首次删去第i条边后得到的最大分
*/

/*
算法描述：
*/

void MIN_MAX( int n, int i, int s, int j, int &minf, int &maxf, int ***m, char* op )
{
	
	int e[5];
	int a,b,r,c,d; 
	a = m[i][s][0];
	b = m[i][s][1];
	r = ( i + s - 1 ) % n + 1;
	c = m[r][j-s][0];
	d = m[r][j-s][1];
	if ( op[r] == '+' )
	{
		minf = a + c;
		maxf = b + d;
	}
	else
	{
		e[1] = a * c;
		e[2] = a * d;
		e[3] = b * c;
		e[4] = b * d;
		minf = e[1];
		maxf = e[1];
		for( int r = 2; r < 5; ++r )
		{
			if ( minf > e[r] )
			{
				minf = e[r];
			}

			if ( maxf < e[r] )
			{
				maxf = e[r];
			}
		}
	}
}

int Poly_Max( int n, int ***m, char* op )
{
	int minf,maxf;
	for( int j = 2; j <= n; ++j )
	{
		for( int i = 1; i <= n; ++i )
		{
			for( int s = 1; s < j; ++s )
			{
				MIN_MAX( n, i, s, j, minf, maxf, m, op );
				
				if ( m[i][j][0] > minf )
				{
					m[i][j][0] = minf;
				}
				if ( m[i][j][1] < maxf )
				{
					m[i][j][1] = maxf;
				}
			}
		}
	}

	int temp = m[1][n][1];
	cout<<"从1开始"<<n<<"个数长的的最大值"<<m[1][n][1]<<endl;
	for( int i = 2; i <= n; ++i )
	{
		cout<<"从"<<i<<"开始"<<n<<"个数长的的最大值"<<m[i][n][1]<<endl;
		if ( temp < m[i][n][1] )
		{
			temp = m[i][n][1];
		}
	}

	return temp;
}

int main()
{
	int n = 4;
	int ***m = 0;
	m = new int**[n+1];
	int i;
	for( i = 0; i <= n; ++i )
	{
		m[i] = new int*[n+1];
		for( int j = 0; j <= n; ++j )
		{
			m[i][j] = new int[3];
			for( int k = 0; k <= 2; ++k )
			{
				m[i][j][k] = 0;
			}
		}
	}

	char* op = new char[n+1];
	op[1] = '+';
	op[2] = '+';
	op[3] = '*';
	op[4] = '*';

	int v[5];
	v[1] = 7;
	v[2] = 4;
	v[3] = 2;
	v[4] = 5;

	for( int u = 1; u <= n; ++u )
	{
		m[u][1][0] = v[u];
		m[u][1][1] = v[u];
	}

	cout<<Poly_Max( n, m, op )<<endl;

	return 0;
}