动态规划---例题6.多边形游戏

一.题目描述

多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。

游戏第1步，将一条边删除。
随后n-1步按以下方式操作：
(1)选择一条边E以及由E连接着的2个顶点V1和V2；
(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。

最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。
问题:对于给定的多边形，计算最高得分。

例子:

二.解题思路

1.最优子结构性质

在所给多边形中，从顶点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]处将链分割为2个子链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

• 当op[i+s]='+'时，显然有a+c≤m≤b+d
• 当op[i+s]='*'时，有min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd}

换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。

2.递归求解

由前面的分析可知，为了求链合并的最大值，必须同时求子链合并的最大值和最小值。
设m[i,j,0]是链p(i,j)合并的最小值，m[i,j,1]是最大值。
若最优合并在op[i+s]处将p(i,j)分为2个长度小于j的子链p(i,s)和p(i+s,j-s) (s和j-s均表示长度)
为叙述方便，记 a=m[i, s,0]，b=m[i, s,1]，c=m[i+s,j-s,0]，d=m[i+s,j-s,0]

• 当op[i+s]=‘+’时，m[i,j,0]=a+c，m[i,j,1]=b+d
• 当op[i+s]=‘*’时， m[i,j,0]=min{ac,ad,bc,bd}，m[i,j,1]=max{ac,ad,bc,bd}

综合以上两点，将p(i,j)在op[i+s]处断开的最大值为maxf(i,j,s)，最小值为minf(i,j,s)，则:

由于子链的长度s有1≤s≤j-1的j-1种可能(只要保证小于原链长j即可)，由此可知:(注:此处应当为 1<= s <= j-1)

初始边界值显然为m[i,1,0]=v[i], m[i,1,1]=v[i], 1≤i≤n。

代码如下:

// // 多边形游戏
#include
using namespace std;
#define NMAX 100
int N, m[NMAX+1][NMAX+1][2], v[NMAX+1];  //m[i][j][0],起始顶点为i,顶点个数为j(链长)
char op[NMAX+1];
int k[NMAX+1][NMAX+1][2];  //表示p(i, j)的第一次划分位置,即顶点为i,链长为j时,划分得到最小值时的位置以及划分得到最大值时的位置

void MinMax(int n, int i, int s, int j, int &minf, int &maxf);
int PolyMax(int n, int &p);
void Show();
int main()
{   
    int p;
    cout<<"请输入多边形顶点数: ";
    cin>>N;
    for(int i=1; i<=N; i++)
    {
        cout<<"请输入多边形顶点"<>v[i];
        m[i][1][0]=v[i];//初始化
        m[i][1][1]=v[i];
        cout<<"请输入多边形边"<>op[i];
    }
    int ans = PolyMax(N, p);
    cout<<"多边形游戏首次删除第"<e[r]) minf = e[r];
            if(maxfminf) m[i][j][0] = minf;  //不断更新数组
                if(m[i][j][1]