文章目录

算法分析1.问题描述2.算法设计2.1最优子结构性质2.2递归求解 3.算法描述4.最优合并顺序5.复杂度分析6.测试7.项目发布地址8.References

算法分析

1.问题描述

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

随后n-1步按以下方式操作：

（1）选择一条边E以及由E连接着的两个顶点$V_1$和$V_2$;

（2）用一个新的顶点取代边E以及由E连接着的两个顶点$V_1$和$V_2$。将由顶点$V_1$和$V_2$的整数值通过边E上的运算得到的结果赋予新顶点。

最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。

问题：对于给定的多边形，计算最高分。

2.算法设计

2.1最优子结构性质

设所给的多边形的顶点和边的顺时针序列为 $$op[1],v[1],op[2],v[2],...,op[n],v[n]$$ 其中，$op[i]$表示第$i$条边所对应的运算符，$v[i]$表示第$i$个顶点上的数组，$i=1\sim n$。

在所给多边形中，从顶点$i(1\le i\le n)$开始，长度为$j$(链中有$j$)个顶点的顺时针链$p(i+s)$可表示为 $$v[i],op[i+1],...,v[i+j-1]$$ 如果这条链的最后一次合并运算在$op[i+s]$处发生$(1\le s\le j-1)$，则可以在$op[i+s]$处将链分割为两个子链$p(i,s)$和$p(i+s,j-s)$。

设$m_1$是对子链$p(i,s)$的任意一种合并方式得到的值，而$a$和$b$分别是在所有可能的合并中得到的最小值和最大值。$m_2$是$p(i+s,j-s)$的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有 $$a\le m_1\le b,c\le m_2\le d$$ 由于子链$p(i,s)$和$p(i+s,j-s)$的合并方式决定了$p(i,j)$在$op[i+s]$处断开后的合并方式，在$op[i+s]$处合并后其值为 $$m=(m_1)op[i+s](m_2)$$

当$op[i+s]{=}^{\prime }{+}^{\prime }$时，显然有 $$a+c\le m\le b+d$$

当$op[i+s]{=}^{\prime }{\ast }^{\prime }$时，由于$v[i]$可取负整数，子链的最大值相乘未必能得到主链的最大值。但最大值一定是在边界点达到，即 $$min\left\{ac,ad,bc,bd\right\}\le m\le max\left\{ac,ad,bc,bd\right\}$$ 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。例如，当$m=ac$时，最大主链由它的两条最小链组成；同理当m=bd时，最大主链由它的两条最大子链组成。

2.2递归求解

为了求链合并的最大值，必须同时求子链合并的最大值和最小值。

设$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$的子链的最大值和最小值均已计算出。记 $$\begin{gathered} 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] \end{gathered}$$ （1）当$op[i+s]{=}^{\prime }{+}^{\prime }$时， $$\begin{gathered} m[i,j,0]=a+c \\ m[i,j,1]=b+d \end{gathered}$$ （2）当$op[i+s]{=}^{\prime }{\ast }^{\prime }$时， $$\begin{gathered} m[i,j,0]=min\left\{ac,ad,bc,bd\right\} \\ m[i,j,1]=min\left\{ac,ad,bc,bd\right\} \end{gathered}$$ 综合(1)和(2)，将$p(i,j)$在$op[i+s]$处断开的最大值记为$maxf(i,j,s)$，最小值记为$minf(i,j,s)$，则 $$minf(i,j,s)=\{\begin{array}{c}a+cop[i+s]{=}^{\prime }{+}^{\prime }\\ min\left\{ac,ad,bc,bd\right\}op[i+s]{=}^{\prime }{\ast }^{\prime }\end{array}$$

$$maxf(i,j,s)=\{\begin{array}{c}b+dop[i+s]{=}^{\prime }{+}^{\prime }\\ min\left\{ac,ad,bc,bd\right\}op[i+s]{=}^{\prime }{\ast }^{\prime }\end{array}$$

由于最优断开位置$s$有$1\le s\le j-1$的j-1种情况，由此可知 $$\begin{gathered} m[i,j,0]=\underset{i\le s<j}{\min }\left\{minf(i,j,s)\right\}1\le i,j\le n \\ m[i,j,1]=\underset{i\le s<j}{\max }\left\{maxf(i,j,s)\right\}1\le i,j\le n \end{gathered}$$ 初始边界为 $$\begin{gathered} m[i,1,0]=v[i]1\le i\le n \\ m[i,1,1]=v[i]1\le i\le n \end{gathered}$$ $m[i,n,1]$即为游戏首次删去第$i$条边后得到的最大得分。

3.算法描述

import java.util.HashMap; import java.util.Scanner; import java.util.Stack; public class PloygonAgent { private int n; //多边形边数 private char[] op; //每条边的对应的操作（从1开始计数） private int[] v; //每个顶点数值（从1开始计数） private long[][][] m; //m[i][n][1]：代表一开始删除第i条边，长度为n的链（包含n个顶点），所能得到的最大值 //m[i][n][0]：代表一开始删除第i条边，长度为n的链，所能得到的最小值 private int[][][] cut; //记录合并点的数组 private Stack<Integer> stack; //用栈保存合并边的顺序 private int firstDelEdge; //记录最优情况下，第1条删除的边 private long bestScore; //记录最优得分 public PloygonAgent(int n, long[][][] m, char[] op, int[] v){ this.n = n; this.m = m; this.op = op; this.v = v; this.cut = new int[n+1][n+1][2]; this.stack = new Stack<>(); } private HashMap<String, Long> minMax(int i, int s, int j, HashMap<String, Long> resMap){ int r = (i+s-1) % n + 1; long a = m[i][s][0], b = m[i][s][1], c = m[r][j-s][0], d = m[r][j-s][1]; if(op[r] == '+'){ resMap.put("minf", a+c); resMap.put("maxf", b+d); }else{ long[] e = new long[]{0, a*c, a*d, b*c, b*d}; long 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]; } resMap.put("minf", minf); resMap.put("maxf", maxf); } return resMap; } private long polyMax(){ HashMap<String, Long> resMap = new HashMap<>(); for (int j = 2; j <= n; j++){ //链的长度 for(int i = 1; i<= n; i++){ //删除第i条边 m[i][j][0] = Long.MAX_VALUE; m[i][j][1] = Long.MIN_VALUE; for(int s = 1; s < j; s++){ //断开的位置 resMap = this.minMax(i, s, j, resMap); if(m[i][j][0] > resMap.get("minf")){ m[i][j][0] = resMap.get("minf"); cut[i][j][0] = s; //记录该链取得最小值的断点 } if(m[i][j][1] < resMap.get("maxf")){ m[i][j][1] = resMap.get("maxf"); cut[i][j][1] = s; //记录该链取得最大值的断点 } } } } bestScore = m[1][n][1]; firstDelEdge = 1; //一开始删除的边，初始化为第一条边 for (int i = 2; i <= n; i++){ if(bestScore < m[i][n][1]){ bestScore = m[i][n][1]; firstDelEdge = i; //如果一开始删除第i边有更优的结果，则更新 } } for(int i=1; i<=n; i++){ //一开始删除第i条边所能得到的最大分数 System.out.println("i=" + i + " " + m[i][n][1]); } System.out.println("firstDelEdge=" + firstDelEdge); getBestSolution(firstDelEdge, n, true); while (!stack.empty()){ //打印在删除第firstDelEdge条边后的最优合并顺序 System.out.println("stack--> " + String.valueOf(stack.pop())); } return bestScore; } /** * 获取最优的合并序列，存入stack中 * @param i 表示子链从哪个顶点开始 * @param j 子链的长度（如j=2，表示链中有两个顶点） * @param needMax 是否取链的最大值，如果传入值为false，则取子链的最小值 */ private void getBestSolution(int i, int j, boolean needMax){ int s,r; if(j == 1) return; //链中只有一个顶点，直接返回 if(j == 2){ s = cut[i][j][1]; r = (i+s-1) % n + 1; stack.push(r); return; //只有两个顶点时，没有子链，无须递归 } //链中有两个以上的顶点时，将最优的边入栈 s = needMax ? cut[i][j][1] : cut[i][j][0]; r = (i+s-1) % n + 1; stack.push(r); if(this.op[r] == '+'){ //当合并计算为"+"操作时 if(needMax){ //如果合并得到的父链需要取得最大值 getBestSolution(i, s, true); getBestSolution(r, j-s, true); }else { //如果合并得到的父链需要取得最小值 getBestSolution(i, s, false); getBestSolution(r, j-s, false); } }else{ //当合并计算为"*"操作时 long a = m[i][s][0], b = m[i][s][1], c = m[r][j-s][0], d = m[r][j-s][1]; long[] e = new long[]{0, a*c, a*d, b*c, b*d}; long mergeMax = e[1], mergeMin = e[1]; for(int k=2; k<=4; k++){ if(e[k] > mergeMax) mergeMax = e[k]; if(e[k] < mergeMin) mergeMin = e[k]; } long merge = (needMax) ? mergeMax : mergeMin; //判断合并得到的父链是取最大还是取最小 if(merge == e[1]){ //子链1和子链2都取最小 getBestSolution(i, s, false); getBestSolution(r, j-s, false); }else if(merge == e[2]){ //子链1取最小，子链2取最大 getBestSolution(i, s, false); getBestSolution(r, j-s, true); }else if(merge == e[3]){ //子链1取最大，子链2取最小 getBestSolution(i, s, true); getBestSolution(r, j-s, false); }else { //子链1和子链2都取最大 getBestSolution(i, s, true); getBestSolution(r, j-s, true); } } } private void showPolygon(){ StringBuilder midBuilder = new StringBuilder(); StringBuilder botBuilder = new StringBuilder(); for(int i=1; i<v.length-1; i++){ midBuilder.append("|").append(String.valueOf(v[i])).append("|"); midBuilder.append("--").append(op[i + 1]).append("--"); } midBuilder.append("|").append(String.valueOf(v[v.length - 1])).append("|"); botBuilder.append(" "); for (int i=1; i<midBuilder.length()-1; i++){ if(i == 1 || i == midBuilder.length()-2) botBuilder.append("|"); else if(i == (midBuilder.length()-1) / 2) botBuilder.append(op[1]); else botBuilder.append("_"); } System.out.println(midBuilder.toString()); System.out.println(botBuilder.toString()); } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ int n = scanner.nextInt(); long[][][] m = new long[n+1][n+1][2]; char[] op = new char[n+1]; int[] v = new int[n+1]; for(int i=1; i<=n; i++){ op[i] = scanner.next().charAt(0); v[i] = scanner.nextInt(); } PloygonAgent ploygonAgent = new PloygonAgent(n, m, op, v); ploygonAgent.showPolygon(); for (int i=1; i<=n; i++){ m[i][1][0] = m[i][1][1] = v[i]; } long result = ploygonAgent.polyMax(); System.out.println("BestScore=" + result); } } }

4.最优合并顺序

在上述算法中，为了能简单地得到一个最优的合并顺序，使用了一个cut[][][]数组来记录断点位置。

其中只在m[i][j][0]或m[i][j][1]进行更新时，相应地也进行更新，保证cut[i][j][0]为m[i][j][0]的最优断点，cut[i][j][1]为m[i][j][1]的最优断点。

这里需要说明的是，cut[i][j][]中保存的s，指的是距离顶点i的距离，若s=1，即从说明从i顶点开始（包括i顶点）只包含一个顶点，也就说要从i顶点连着的顺时针的边断开。

其实，计算得到最优分数的过程是一个自底向上的过程，而寻找最优合并顺序则相反，是一个自顶向下的过程。

基本的思路就是，使用一个栈来保存合并边的编号

(1)从最后的主链开始，找到最优的合并边，入栈(2)判断合并边的符号，如果是‘+’，转(3)；如果是‘*’，转(4)(3)如果为+，判断主链需要最大还是最小 如需最大，则递归取两条子链的最大；否则，递归取两条子链的最小 (4)如果为*，判断主链需要最大还是最小 如需最大，则在{ac, ad, bc, bd}取最大的情况，进行相应递归调用（如ac，则递归时，两条子链都需要取最小值）否则，则在{ac, ad, bc, bd}取最小的情况，进行相应递归调用

5.复杂度分析

寻找最优合并顺序

递归深度最好的情况是$logn$，也就说每次都恰好是对半进行合并；最坏情况是n-1，每次都合并单个顶点;

一次递归的过程中，计算时间为常数级别C，所以整个时间复杂度为递归调用次数，即$O(C(n-1))=O(n)$

总的时间复杂度

动规过程需要$O(n^3)$计算时间，加寻找最优合并顺序的时间$O(n)$，总的时间复杂度为$O(n^3)$

6.测试

Case 1

Input

5 * -5 + -2 * -8 * -5 + 8

Output

|-5|--+--|-2|--*--|-8|--*--|-5|--+--|8| |_________________*_________________| i=1 168 i=2 480 i=3 488 i=4 488 i=5 120 firstDelEdge=3 stack--> 2 stack--> 1 stack--> 5 stack--> 4 BestScore=488

Case 2

Input

5 * -6 + -7 * 0 * 4 + -2

Ouput

|-6|--+--|-7|--*--|0|--*--|4|--+--|-2| |________________*_________________| i=1 26 i=2 12 i=3 26 i=4 16 i=5 48 firstDelEdge=5 stack--> 3 stack--> 2 stack--> 4 stack--> 1 BestScore=48

Case 3

Input

6 + 5 * 3 + -2 + 1 * -10 * -2

Ouput

|5|--*--|3|--+--|-2|--+--|1|--*--|-10|--*--|-2| |_____________________+_____________________| i=1 280 i=2 50 i=3 130 i=4 73 i=5 74 i=6 63 firstDelEdge=1 stack--> 6 stack--> 4 stack--> 2 stack--> 3 stack--> 5 BestScore=280

Case 4

Input

8 + -2 + 9 * -5 + -4 * -5 * 0 + 7 * -5

Ouput

|-2|--+--|9|--*--|-5|--+--|-4|--*--|-5|--*--|0|--+--|7|--*--|-5| |_____________________________+______________________________| i=1 2905 i=2 3969 i=3 630 i=4 5080 i=5 3080 i=6 3080 i=7 200 i=8 3080 firstDelEdge=4 stack--> 1 stack--> 8 stack--> 7 stack--> 6 stack--> 2 stack--> 3 stack--> 5 BestScore=5080

Case 5

Input

9 * 0 * -10 + 8 * -4 + 3 * -7 + 7 * -3 * -4

Ouput

|0|--*--|-10|--+--|8|--*--|-4|--+--|3|--*--|-7|--+--|7|--*--|-3|--*--|-4| |__________________________________*__________________________________| i=1 2816 i=2 273 i=3 2000 i=4 2816 i=5 5376 i=6 899 i=7 19257 i=8 2758 i=9 2816 firstDelEdge=7 stack--> 4 stack--> 2 stack--> 3 stack--> 1 stack--> 5 stack--> 6 stack--> 9 stack--> 8 BestScore=19257

Case 6

Input

4 + -7 + 4 * 2 * 5

Ouput

|-7|--+--|4|--*--|2|--*--|5| |___________+____________| i=1 33 i=2 33 i=3 7 i=4 6 firstDelEdge=1 stack--> 4 stack--> 3 stack--> 2 BestScore=33

7.项目发布地址

http://39.108.70.146:8080/PolygonGame/index.html https://github.com/wylu/PolygonGame

8.References

王晓东《算法设计与分析》第三版