多边形游戏

问题简介

• 首先呢，介绍一下多边形游戏是个什么东东
• 多边形游戏是一个单人玩的游戏，开始时有一个由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) = 9
m(1,1,0) = 9
m(2,1,1) = -4
m(2,1,0) = -4
m(3,1,1) = 9
m(3,1,0) = 9
m(4,1,1) = 10
m(4,1,0) = 10
m(5,1,1) = -10
m(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) = 5
m(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) = 5
m(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) = 19
m(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)} = -100
m(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) = -1
m(5,2,0) = m(5,1,0) + m(1,1,0) = -1

m ( 1 , 3 ) = { m ( 1 , 1 ) o p ( 2 ) m ( 2 , 2 ) m ( 1 , 2 ) o p ( 3 ) m ( 3 , 1 ) m(1,3) =

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))

m ( 2 , 3 ) = { m ( 2 , 1 ) o p ( 3 ) m ( 3 , 2 ) m ( 2 , 2 ) o p ( 4 ) m ( 4 , 1 ) m(2,3) =

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))

m ( 3 , 3 ) = { m ( 3 , 1 ) o p ( 4 ) m ( 4 , 2 ) m ( 3 , 2 ) o p ( 5 ) m ( 5 , 1 ) m(3,3) =

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))

m ( 4 , 3 ) = { m ( 4 , 1 ) o p ( 5 ) m ( 5 , 2 ) m ( 4 , 2 ) o p ( 1 ) m ( 1 , 1 ) m(4,3) =

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))

m ( 5 , 3 ) = { m ( 5 , 1 ) o p ( 1 ) m ( 1 , 2 ) m ( 5 , 2 ) o p ( 2 ) m ( 2 , 1 ) m(5,3) =

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))

m ( 1 , 4 ) = { m ( 1 , 1 ) o p ( 2 ) m ( 2 , 3 ) m ( 1 , 2 ) o p ( 3 ) m ( 3 , 2 ) m ( 1 , 3 ) o p ( 4 ) m ( 4 , 1 ) m(1,4) =

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))

m ( 2 , 4 ) = { m ( 2 , 1 ) o p ( 3 ) m ( 3 , 3 ) m ( 2 , 2 ) o p ( 4 ) m ( 4 , 2 ) m ( 2 , 3 ) o p ( 5 ) m ( 5 , 1 ) m(2,4) =

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))

m ( 3 , 4 ) = { m ( 3 , 1 ) o p ( 4 ) m ( 4 , 3 ) m ( 3 , 2 ) o p ( 5 ) m ( 5 , 2 ) m ( 3 , 3 ) o p ( 1 ) m ( 1 , 1 ) m(3,4) =

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))

m ( 4 , 4 ) = { m ( 4 , 1 ) o p ( 5 ) m ( 5 , 3 ) m ( 4 , 2 ) o p ( 1 ) m ( 1 , 2 ) m ( 4 , 3 ) o p ( 2 ) m ( 2 , 1 ) m(4,4) =

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))

m ( 5 , 4 ) = { m ( 5 , 1 ) o p ( 1 ) m ( 1 , 3 ) m ( 5 , 2 ) o p ( 2 ) m ( 2 , 2 ) m ( 5 , 3 ) o p ( 3 ) m ( 3 , 1 ) m(5,4) =

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))

m ( 1 , 5 ) = { m ( 1 , 1 ) o p ( 2 ) m ( 2 , 4 ) m ( 1 , 2 ) o p ( 3 ) m ( 3 , 3 ) m ( 1 , 3 ) o p ( 4 ) m ( 4 , 2 ) m ( 1 , 4 ) o p ( 5 ) m ( 5 , 1 ) m(1,5) =

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))

m ( 2 , 5 ) = { m ( 2 , 1 ) o p ( 3 ) m ( 3 , 4 ) m ( 2 , 2 ) o p ( 4 ) m ( 4 , 3 ) m ( 2 , 3 ) o p ( 5 ) m ( 5 , 2 ) m ( 2 , 4 ) o p ( 1 ) m ( 1 , 1 ) m(2,5) =

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))

m ( 3 , 5 ) = { m ( 3 , 1 ) o p ( 4 ) m ( 4 , 4 ) m ( 3 , 2 ) o p ( 5 ) m ( 5 , 3 ) m ( 3 , 3 ) o p ( 1 ) m ( 1 , 2 ) m ( 3 , 4 ) o p ( 2 ) m ( 2 , 1 ) m(3,5) =

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))

m ( 4 , 5 ) = { m ( 4 , 1 ) o p ( 5 ) m ( 5 , 4 ) m ( 4 , 2 ) o p ( 1 ) m ( 1 , 3 ) m ( 4 , 3 ) o p ( 2 ) m ( 2 , 2 ) m ( 4 , 4 ) o p ( 3 ) m ( 3 , 1 ) m(4,5) =

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))

m ( 5 , 5 ) = { m ( 5 , 1 ) o p ( 1 ) m ( 1 , 4 ) m ( 5 , 2 ) o p ( 2 ) m ( 2 , 3 ) m ( 5 , 3 ) o p ( 3 ) m ( 3 , 2 ) m ( 5 , 4 ) o p ( 4 ) m ( 4 , 1 ) m(5,5) =

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)} = 40
max = 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];
		}
	}
}
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
 

最大值: 33
最小值: -35

  
 

  
1
  
2
 

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

文章来源: ruochen.blog.csdn.net，作者：若尘，版权归原作者所有，如需转载，请联系作者。

原文链接：ruochen.blog.csdn.net/article/details/105165505