多边形游戏

问题简介

• 首先呢，介绍一下多边形游戏是个什么东东

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

• 游戏步骤：

• 将一条边删除

• 选择一条边 E 及由 E 连接的 2 个顶点 V1 和 V2

• 用一个新的顶点取代边 E 以及由 E 连接着的 2 个顶点 V1 和 V2。将由顶点 V1 和 V2 的整数值通过边 E 上的运算得到的结果赋予新顶点

• 重复以上步骤，直到所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值

我们的问题是： 根据给定的多边形，计算最高分和最底分

问题分析

• 最优子结构性质

• 这里呢，它是满足最优子结构性质的，我们不做过多的解释，直接看它的求解方法

• 递归求解

• 首先，我们在 p(i, j)在 op[i+s]处断开， 最大值记为 maxf(i,j,s)，最小值记为 minf(i,j,s)

• 因为只有加法和乘法，加法比较简单。对于乘法，可能存在负数，所以我们要对所有可能的结果做讨论，为了计算方便，我们可以定义如下表示 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]

• 当 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}

• 因此可有如下公式

  
  
  
  

• 至于 s 的断开位置，可以取 1 到 j - 1， 如下

  
  
  

接下来，就是超超超超级详细的解题步骤

超详细解题步骤

这里，我们举了这样一个栗子

详细步骤如下

m(1,1,1) = 9m(1,1,0) = 9m(2,1,1) = -4m(2,1,0) = -4m(3,1,1) = 9m(3,1,0) = 9m(4,1,1) = 10m(4,1,0) = 10m(5,1,1) = -10m(5,1,0) = -10

m(1,2) = m(1,1)op(2)m(2,1)op(2) = "+"m(1,2,1) = m(1,1,1) + m(2,1,1) = 5m(1,2,0) = m(1,1,0) + m(2,1,0) = 5

m(2,2) = m(2,1)op(3)m(3,1)op(3) = "+"m(2,2,1) = m(2,1,1) + m(3,1,1) = 5m(2,2,0) = m(2,1,0) + m(3,1,0) = 5

m(3,2) = m(3,1)op(4)m(4,1)op(4) = "+"m(3,2,1) = m(3,1,1) + m(4,1,1) = 19m(3,2,0) = m(3,1,0) + m(4,1,0) = 19

m(4,2) = m(4,1)op(5)m(5,1)op(5) = "*"m(4,2,1) = max{m(4,1,1)*m(5,1,1), m(4,1,1)*m(5,1,0), m(4,1,0)*m(5,1,1), m(4,1,0)*m(5,1,0)} = -100m(4,2,0) = min{m(4,1,1)*m(5,1,1), m(4,1,1)*m(5,1,0), m(4,1,0)*m(5,1,1), m(4,1,0)*m(5,1,0)} = -100

m(5,2) = m(5,1)op(1)m(1,1)m(5,2,1) = m(5,1,1) + m(1,1,1) = -1m(5,2,0) = m(5,1,0) + m(1,1,0) = -1

op(2) = "+"op(3) = "+"m(1,3,1) = max{m(1,1,1)+m{2,2,1}, m(1,2,1)+m(3,1,1)} = 14 (m(1,1,1)+m(2,2,1))m(1,3,0) = min{m(1,1,0)+m{2,2,0}, m(1,2,0)+m(3,1,0)} = 14 (m(1,1,0)+m(2,2,0))

op(3) = "+"op(4) = "+"m(2,3,1) = max{m(2,1,1)+m(3,2,1), m(2,2,1)+m(4,1,1)} = 15 (m(2,1,1)+m(3,2,1))m(2,3,0) = min{m(2,1,0)+m(3,2,0), m(2,2,0)+m(4,1,0)} = 15 (m(2,1,0)+m(3,2,0))

op(4) = "+"op(5) = "*"m(3,3,1) = max{m(3,1,1)+m(4,2,1), max{m(3,2,1)*m(5,1,1), m(3,2,1)*m(5,1,0), m(3,2,0)*m(5,1,1), m(3,2,0)*m(5,1,0)}} = -91 (m(3,1,1)+m(4,2,1))m(3,3,0) = min{m(3,1,0)+m(4,2,0), min{m(3,2,1)*m(5,1,1), m(3,2,1)*m(5,1,0), m(3,2,0)*m(5,1,1), m(3,2,0)*m(5,1,0)}} = -190 (m(3,2,1)*m(5,1,1))

op(5) = "*"op(1) = "+"m(4,3,1) = max{max{m(4,1,1)*m(5,2,1), m(4,1,1)*m(5,2,0), m(4,1,0)*m(5,2,1), m(4,1,0)*m(5,2,0)}, m(4,2,1)+m(1,1,1)} = -10 (m(4,1,1)*m(5,2,1))m(4,3,0) = min{min{m(4,1,1)*m(5,2,1), m(4,1,1)*m(5,2,0), m(4,1,0)*m(5,2,1), m(4,1,0)*m(5,2,0)}, m(4,2,0)+m(1,1,0)} = -91 (m(4,2,0)+m(1,1,0))

op(1) = "+"op(2) = "+"m(5,3,1) = max{m(5,1,1)+m(1,2,1), m(5,2,1)+m(2,1,1)} = -5 (m(5,1,1)+m(1,2,1))m(5,3,0) = min{m(5,1,0)+m(1,2,0), m(5,2,0)+m(2,1,0)} = -5 (m(5,1,0)+m(1,2,0))

op(2) = "+"op(3) = "+"op(4) = "+"m(1,4,1) = max{m(1,1,1)+m(2,3,1), m(1,2,1)+m(3,2,1), m(1,3,1)+m(4,1,1)} = 24 (m(1,1,1)+m(1,2,1))m(1,4,0) = min{m(1,1,0)+m(2,3,0), m(1,2,0)+m(3,2,0), m(1,3,0)+m(4,1,0)} = 24 (m(1,1,0)+m(2,3,0))

op(3) = "+"op(4) = "+"op(5) = "*"m(2,4,1) = max{m(2,1,1)+m(3,3,1), m(2,2,1)+m(4,2,1), max{m(2,3,1)*m(5,1,1), m(2,3,1)*m(5,1,0), m(2,3,0)*m(5,1,1), m(2,3,0)*m(5,1,0)}} = -95 (m(2,1,1)+m(3,3,1))m(2,4,0) = min{m(2,1,0)+m(3,3,0), m(2,2,0)+m(4,2,0), min{m(2,3,1)*m(5,1,1), m(2,3,1)*m(5,1,0), m(2,3,0)*m(5,1,1), m(2,3,0)*m(5,1,0)}} = -194 (m(2,1,0)+m(3,3,0))

op(4) = "+"op(5) = "*"op(1) = "+"m(3,4,1) = max{m(3,1,1)+m(4,3,1), max{m(3,2,1)*m(5,2,1), m(3,2,1)*m(5,2,0), m(3,2,0)*m(5,2,1), m(3,2,0)*m(5,2,0)}, m(3,3,1)+m(1,1,1)} = -1 (m(3,1,1)+m(4,3,1))m(3,4,0) = min{m(3,1,0)+m(4,3,0), min{m(3,2,1)*m(5,2,1), m(3,2,1)*m(5,2,0), m(3,2,0)*m(5,2,1), m(3,2,0)*m(5,2,0)}, m(3,3,0)+m(1,1,0)} = -181 (m(3,3,0)+m(1,1,0))

op(5) = "*"op(1) = "+"op(2) = "+"m(4,4,1) = max{max{m(4,1,1)*m(5,3,1), m(4,1,1)*m(5,3,0), m(4,1,0)*m(5,3,1), m(4,1,0)*m(5,3,0)}, m(4,2,1)+m(1,2,1), m(4,3,1)+m(2,1,1)} = -14 (m(4,3,1)+m(2,1,1))m(4,4,0) = min{min{m(4,1,1)*m(5,3,1), m(4,1,1)*m(5,3,0), m(4,1,0)*m(5,3,1), m(4,1,0)*m(5,3,0)}, m(4,2,0)+m(1,2,0), m(4,3,0)+m(2,1,0)} = -95 (m(4,2,0)+m(1,2,0))

op(1) = "+"op(2) = "+"op(3) = "+"m(5,4,1) = max{m(5,1,1)+m(1,3,1), m(5,2,1)+m(2,2,1), m(5,3,1)+m(3,1,1)} = 4 (m(5,1,1)+m(1,3,1))m(5,4,0) = min{m(5,1,0)+m(1,3,0), m(5,2,0)+m(2,2,0), m(5,3,0)+m(3,1,0)} = 4 (m(5,1,0)+m(1,3,0))

op(2) = "+"op(3) = "+"op(4) = "+"op(5) = "*"m(1,5,1) = max{m(1,1,1)+m(2,4,1), m(1,2,1)+m(3,3,1), m(1,3,1)+m(4,2,1), max{m(1,4,1)*m(5,1,1), m(1,4,1)*m(5,1,0), m(1,4,0)*m(5,1,1), m(1,4,0)*m(5,1,0)}} = -86 (m(1,1,1)+m(2,4,1))m(1,5,0) = min{m(1,1,0)+m(2,4,0), m(1,2,0)+m(3,3,0), m(1,3,0)+m(4,2,0), min{m(1,4,1)*m(5,1,1), m(1,4,1)*m(5,1,0), m(1,4,0)*m(5,1,1), m(1,4,0)*m(5,1,0)}} = -240 (m(1,4,1)*m(5,1,1))

op(3) = "+"op(4) = "+"op(5) = "*"op(1) = "+"m(2,5,1) = max{m(2,1,1)+m(3,4,1), m(2,2,1)+m(4,3,1), max{m(2,3,1)*m(5,2,1), m(2,3,1)*m(5,2,0), m(2,3,0)*m(5,2,1), m(2,3,0)*m(5,2,0)}, m(2,4,1)+m(1,1,1)} = -5 (m(2,1,1)+m(3,4,1))m(2,5,0) = min{m(2,1,0)+m(3,4,0), m(2,2,0)+m(4,3,0), min{m(2,3,1)*m(5,2,1), m(2,3,1)*m(5,2,0), m(2,3,0)*m(5,2,1), m(2,3,0)*m(5,2,0)}, m(2,4,0)+m(1,1,0)} = -185 (m(2,1,0)+m(3,4,0))

op(4) = "+"op(5) = "*"op(1) = "+"op(2) = "+"m(3,5,1) = max{m(3,1,1)+m(4,4,1), max{m(3,2,1)*m(5,3,1), m(3,2,1)*m(5,3,0), m(3,2,0)*m(5,3,1), m(3,2,0)*m(5,3,0)}, m(3,3,1)+m(1,2,1), m(3,4,1)+m(2,1,1)} = -5 (m(3,1,1)+m(4,4,1))m(3,5,0) = min{m(3,1,0)+m(4,4,0), min{m(3,2,1)*m(5,3,1), m(3,2,1)*m(5,3,0), m(3,2,0)*m(5,3,1), m(3,2,0)*m(5,3,0)}, m(3,3,0)+m(1,2,0), m(3,4,0)+m(2,1,0)} = -185 (m(3,3,0)+m(1,2,0))

op(5) = "*"op(1) = "+"op(2) = "+"op(3) = "+"m(4,5,1) = max{max{m(4,1,1)*m(5,4,1), m(4,1,1)*m(5,4,0), m(4,1,0)*m(5,4,1), m(4,1,0)*m(5,4,0)}, m(4,2,1)+m(1,3,1), m(4,3,1)+m(2,2,1), m(4,4,1)+m(3,1,1)} = 40 (m(4,1,1)*m(5,4,1))m(4,5,0) = min{min{m(4,1,1)*m(5,4,1), m(4,1,1)*m(5,4,0), m(4,1,0)*m(5,4,1), m(4,1,0)*m(5,4,0)}, m(4,2,0)+m(1,3,0), m(4,3,0)+m(2,2,0), m(4,4,0)+m(3,1,0)} = -86 (m(4,2,0)+m(1,3,0))

op(1) = "+"op(2) = "+"op(3) = "+"op(4) = "+"m(5,5,1) = max{m(5,1,1)+m(1,4,1), m(5,2,2)+m(2,3,1), m(5,3,1)+m(3,2,1), m(5,4,1)+m(4,1,1)} = 14 (m(5,1,1)+m(1,4,1))m(5,5,0) = min{m(5,1,0)+m(1,4,0), m(5,2,0)+m(2,3,0), m(5,3,0)+m(3,2,0), m(5,4,0)+m(4,1,0)} = 14 (m(5,1,0)+m(1,4,0))

至此，终于计算完毕，那么：max = max{m(1,5,1), m(2,5,1), m(3,5,1), m(4,5,1), m(5,5,1)} = 40max = min{m(1,5,0), m(2,5,0), m(3,5,0), m(4,5,0), m(5,5,0)} = -240

最后，是 Java 代码的实现过程

Java 代码实现

package PolygonGame;
public class PolygonGame {
  static int n;  // 边和点个数  static int minf, maxf;   static int[] v;  // 点集  static char[] op;  // 边集  static int[][][] m;  // 存放最终计算结果  static int[] result;  // 存放最大值和最小值    public static void main(String[] args) {    n = 4;    // 我的案例是: + -7 + 4 * 2 * 5    v = new int[] {Integer.MIN_VALUE, -7, 4, 2, 5};    op = new char[] {' ', '+', '+', '*', '*'};    m = new int[n + 1][n + 1][2];    for (int i = 1; i <= n; i++) {      // m[i][j][1] 表示起点为i，长度为j的最大值      m[i][1][1] = v[i];      // m[i][j][0] 表示起点为i，长度为j的最小值      m[i][1][0] = v[i];    }    polyMax();    System.out.println("最大值: " + result[0] + "\n最小值: " + result[1]);      }    /**   *    * @param i: 链的起点   * @param s: 断开位置   * @param j: 链的长度   */  public static void minMax(int i, int s, int j) {    int[] e = new int[n + 1];    // 在op(i+s) 处进行分割    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] == '+') {      // 对符号进行判断，加号和乘号的处理方式不同      minf = a + c;      maxf = b + d;    } else {      // 为乘号      // maxf=max{ac, ad, bc, bd}      // minf=min{ac, ad, bc, bd}      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; k++) {        // 查找最大最小值        if (minf > e[k])          minf = e[k];        if (maxf < e[k])          maxf = e[k];      }    }  }    public static void polyMax() {    for(int j = 2; j <= n; j++)  // 总长度遍历      for(int i = 1; i <= n; i++)        for(int s = 1; s < j; s++) {  // 断开位置          // 求m[i][j][1]和m[i][j][0]          minMax(i, s, j);          if(m[i][j][0] > minf)            m[i][j][0] = minf;          if(m[i][j][1] < maxf)            m[i][j][1] = maxf;        }    result = new int[2];    result[0] = m[1][n][1];    result[1] = m[1][n][0];    for(int i = 1; i <= n; i++) {      if (result[0] < m[i][n][1])         result[0] = m[i][n][1];      if (result[1] > m[i][n][0])         result[1] = m[i][n][0];    }  }}

最大值: 33最小值: -35

好了，到此结束。欢迎大家关注我😀