多边形游戏

秒速五厘米 2022-01-15 01:51 286阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

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

1 将一条边删除。

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

(1)选择一条边E以及由E连接着的2个顶点V1和V2；

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

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

--------------------

**思路:**

在所给多边形中，从顶点i(1≤i≤n)开始，长度为j(链中有j个顶点)的顺时针链p(i，j) 可表示为v\[i\]，op\[i+1\]，…，v\[i+j-1\]。

如果这条链的最后一次合并运算在op\[i+s\]处发生(1≤s≤j-1)，则可在op\[i+s\]处将链分割为2个子链p(i，s)和p(i+s，j-s)。

设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\}

换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。

--------------------

**核心思想：**

void PolyMax() { int i, j, k, max; for (j = 1; j < N; j ++) for (i = 0; i < N; i ++) for (k = 0; k < j; k ++) { MinMax(i, j, k); if (m[i][j][0] > minf) m[i][j][0] = minf; if (m[i][j][1] < maxf) m[i][j][1] = maxf; } max = m[0][N - 1][1]; for (i = 1; i < N; i ++) if (max < m[i][N - 1][1]) max = m[i][N - 1][1]; printf("%d\n", max); } void MinMax(int i, int j, int k) { int e[4], l, a = m[i][k][0], b = m[i][k][1], r = (i + k + 1) % N, c = m[r][j - k - 1][0], d = m[r][j - k - 1][1]; if (op[(r - 1 + N) % N] == '+') { minf = a + c; maxf = b + d; } else { e[0] = a * c; e[1] = a * d; e[2] = b * c; e[3] = b * d; minf = e[0]; maxf = e[0]; for (l = 1; l < 4; l ++) { if (minf > e[l]) minf = e[l]; if (maxf < e[l]) maxf = e[l]; } } }

转载于:https://my.oschina.net/u/204616/blog/545249

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/94a5ae0f5a1449b3943b5e779a0b9726.png