0015算法笔记——【动态规划】多边形游戏问题

1、问题描述： 给定 N 个顶点的多边形，每个顶点标有一个整数，每条边上标有 +(加)或是×(乘)号，并且 N 条边按照顺时针 依次编号为 1~N。下图给出了一个 N＝4 个顶点的多边形。 游戏规则 ： (1) 首先， 移走一条边。 (2) 然后进行下面的操作： 选 中一条边 E，该边有两个相邻的顶点， 不妨称为 V1 和 V2。对 V1 和 V2 顶点所标的整数按照 E 上所标运算符号(+或是×)进行运算， 得到一个整 数；用该整数标注一个新顶点，该顶点代替 V1 和 V2 。 持续进行此操 作，直到最后没有边存在，即只剩下一个顶点。该顶点的整数称为此次 游戏的得分(Score)。 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（1N; 18. forfor(intint i=1; iv[i]; 22. m[i][1][0]=v[i]; 23. m[i][1][1]=v[i]; 24. coutop[i]; 26. } 27. cout“多边形游戏首次删除第“p“条边，结果为：“PloyMax(N,p)endl; 28. returnreturn 0; 29. } 30. 31. voidvoid MinMax(intint n,intint i,intint s,intint j,intint 34. intint a=m[i][s][0],b=m[i][s][1]; 35. intint r=(i+s-1)%n+1;//多边形的实际顶点编号 36. intint c=m[r][j-s][0],d=m[r][j-s][1]; 37. 38. ifif(op[r-1]== + ) 39. { 40. minf=a+c; 41. maxf=b+d; 42. } 43. elseelse 44. { 45. e[1]=a*c; 46. e[2]=a*d; 47. e[3]=b*c; 48. e[4]=d*b; 49. minf=e[1]; 50. maxf=e[1]; 51. 52. forfor(intint r=2;re[r])minf=e[r]; 55. ifif(maxfe[r])maxf=e[r]; 56. } 57. } 58. } 59. 60. intint PloyMax(intint n,intint 63. forfor(intint j=2;j=n;j++) //迭代链的长度 64. { 65. forfor(intint i=1;i=n;i++)//迭代首次删掉第 i 条边 66. { 67. forfor(intint s=1 ;sminf) m[i][j][0]=minf; 71. ifif(m[i][j][1]maxf) m[i][j][1]=maxf; 72. } 73. } 74. } 75. 76. intint temp=m[1][n][1]; 77. p=1; 78. 79. forfor(intint i=2 ;i=n; i++) 80. { 81. ifif(tempm[i][n][1]) 82. { 83. temp=m[i][n][1]; 84. p=i; 85. } 86. } 87. returnreturn temp; 88. } 程序运行结果如下：