1.描述：有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。

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

输入：
输入共两行，第一行一个整数n表示顶点个数，第二行共2*n个数，分别为数字和字符。

例如：对于上图中的问题，我们可以这样按输入样例中的例子输入,数学中的“+”号代表加法，小写字母“x”代表乘法。

输出：
一个整数，计算最高得分。

输入样例：
5
10 + -1 x -2 x 3 + -8 x

输出样例：
486

2.问题分析
解决该问题可用动态规划中的最优子结构性质来解。
设所给的多边形的顶点和边的顺时针序列为op[1],v[1],op[2],v[2],op[3],…,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]。

设m1是对子链p[i][s]的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p[i+s][j-s]的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有a≤m1≤b，c≤m2≤d
(1)当op[i+s]=’+’时，显然有a+c≤m≤b+d

　　(2)当op[i+s]=’*’时，有min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd}

换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。例如，当m=ac时，最大主链由它的两条最小主链组成；同理当m=bd时，最大主链由它的两条最大子链组成。无论哪种情形发生，由主链的最优性均可推出子链的最优性。
综上可知多边形游戏问题满足最优子结构的性质。

3.递归求解

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

设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+cm[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)，则

                                           a+c                               op[i+s]='+'minf(i,j,s)=｛                                         min{ac,ad,bc,bd}           op[i+s]='*'b+d                                op[i+s]='+'     maxf(i,j,s)=｛                                               max{ac,ad,bc,bd}          op[i+s]='*'由于多边最优断开位置s有1≤s≤j-1的j-1种情况，由此可知m[i,j,0]=min{minf(i,j,s)}                  1≤i,j≤n  m[i,j,1]=max{maxf(i,j,s)}                  1≤i,j≤n   初始边界显然为m[i,j,0]=v[i]                  1≤i≤nm[i,j,1]=v[i]                  1≤ i≤n

由于多边形是封闭的，在上面的计算中，当i+s>n是，顶点i+s实际编号为(i+s)mod n。按上述递推式计算出的m[i,n,1]即为首次删去第i条边后得到的最大得分。

4.算法描述

基于以上讨论可设计解多边形游戏问题的动态规划算法如下：

       void minMax(int i,int s,int j){          int e[5];int 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]=='t'){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 k=2;k<5 kh>{if(minf>e[k]) minf=e[k];if(maxf}}

}

int polyMax(){
for(int j=2;j<=n;j++)for(int i=1;i<=n;i++)for(int s=1;s{minMax(i,s,j);m[i][j][0]=100000;m[i][j][1]=-100000;if(m[i][j][0]>minf) m[i][j][0]=minf;if(m[i][j][1]}long int temp=m[1][n][1];for(int i=2;i<=n;i++)if(tempreturn temp;

}

【新方法】

本题在处理顺时针循环时的下标时，有一个很妙的方法。即，

                        r=(i+s-1)%n+1

其实，本题从这样编纯属巧合。

当i+s 并不需要减一的时候，用这种方法编就很方便。

如果用传统的方法就是

            if(i==n)       r=n;else r=i%n

这样，以来r=(i+s-1)%n+1就简单了不少。

【参考程序】

#include#includelong int minf,maxf,m[51][51][2];char op[52];int v[51],n;void in(){FILE *in=fopen("polygon2.in","r");fscanf(in,"%d",&n);fgetc(in);for(int i=1;i<=n;i++)fscanf(in,"%c %d ",&op[i],&v[i]);fclose(in);}    void iniM(){for(int i=1;i<=n;i++){m[i][1][0]=v[i];m[i][1][1]=v[i];}}void minMax(int i,int s,int j){int e[5];int 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]=='t'){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 k=2;k<5 kh>{if(minf>e[k]) minf=e[k];if(maxf}}}                                     int polyMax(){for(int j=2;j<=n;j++)for(int i=1;i<=n;i++)for(int s=1;s{minMax(i,s,j);m[i][j][0]=100000;m[i][j][1]=-100000;if(m[i][j][0]>minf) m[i][j][0]=minf;if(m[i][j][1]}long int temp=m[1][n][1];for(int i=2;i<=n;i++)if(tempreturn temp;}int main(){in();iniM();long int max=polyMax();printf("%ld\n",max);system("pause");return 0;}