多边形游戏.cpp

动态规划解一系列经典问题

//多边形游戏

#include <stdio.h>
#include <ctype.h>
#define N 5
char op[N];
int minf, maxf, m[N][N][2];
void PolyMax();
void MinMax(int i, int j, int k);

void main(int argc, char* argv[])
{
	int i;
	char ch;
	printf("Input %d Num & Op:\n",N);
	for (i=0; i<N; i++)
	{
		scanf("%d", &m[i][0][0]);
		m[i][0][1]=m[i][0][0];
		while((ch=getchar()) && isspace(ch));
		op[i]=ch;
	}
	PolyMax();
}

void PolyMax()
{
	int i, j, k, max;
	for (j=1; j<N; j++)
		for (i=0; i<N; i++)
			for (k=0; k<j; k++)
			{
				MinMax(i, j, k);
				if (m[i][j][0]>minf) m[i][j][0]=minf;
				if (m[i][j][1]<maxf) m[i][j][1]=maxf;
			}
			max = m[0][N-1][1];
			for (i=1; i<N; i++)
				if (max<m[i][N-1][1]) max=m[i][N-1][1];
	printf("%d\n", max);
}

void MinMax(int i, int j, int k)
{
	int e[4], l, a=m[i][k][0], b=m[i][k][1];
        int r=(i+k+1) % N,c=m[r][j-k-1][0],d=m[r][j-k-1][1];
	if (op[(r-1+N) % N] == '+')
	{
		minf=a+c;
 		maxf=b+d;
	}
	else
	{
        e[0]=a*c;
        e[1]=a*d;
        e[2]=b*c;
        e[3]=b*d;
        minf=e[0];
        maxf=e[0];
        for (l=1; l<4; l++)
	{
            if (minf>e[l]) minf=e[l];
            if (maxf<e[l]) maxf=e[l];
        }
    }
}