POJ 1179 Polygon
这题好像有一些动规的味道。嗯嗯，比较基础的动规题。个人感觉用 O(n2) 的算法可以解决掉。
原题地址：http://poj.org/problem?id=1179
POJ 1179 多边形
问题描述
Polygon 是一个有关多边形的单人游戏。图 1 就是一个这样的多边形，它的边数 N 为 4. 多边形中每一个顶点都标记了一个整数，每一条边都标记了 +（加号）或 *（乘号）。并且，边被标记了从 1 到 N 的整数。
在第一回合的时候，先拿掉多边形的一条边。接下来的回合中涉及以下几步：
- 选择一条边 E 和它所连接的两个顶点 V1 和 V2；然后……
- 将它们替换成一个新顶点，并且这个新顶点的标签，就是以 V1 和 V2 所标记的数，在边 E 所标记的符号下运算，所得到的结果。
在没有任何边的时候，游戏结束，并且游戏的得分是最后幸存顶点所标记的数字。
考虑图 1 的多边形。玩家第一回合拿掉了第 3 条边。此后，玩家依次选择了第 1 条边，第 4 条边，最后是第 2 条边。他的得分是 0.
写一个程序，对于给出的多边形，计算其可行的最高得分；并且列出所有能够使得游戏取得最高分的，在第一回合被拿掉的边。
输入数据
你的程序需要从标准输入中读取数据，输入数据将描述这个有 N 个顶点的多边形。输入数据共含两行，第一行就是整数 N. 第二行包含从第 1 条到第 N 条边的标签，并且顶点的标签将会穿插在其中（就是，先给出第 1 条边的符号，然后给出与第 1 条边和第 2 条边共连的顶点的数字，再给出第二条边的符号，依此类推，直到与第 N 条边和第 1 条边共连的顶点），这些数据会以一个空格分隔。边的标签会表示成字母 t（表示加号 +）或字母 x（表示乘号 *）。
3 ≤ N ≤ 50
对于每个回合，输入数据能够保证顶点的标签会在 [-32768, 32767] 范围内。
输出数据
你的程序需要把结果输出到标准输出中。第一行，你的程序应输出该多边形能够得到的最高分。第二行，它必须写出所有能够使得游戏取得最高分的，在第一回合被拿掉的边 (all edges that, if removed on the first move, can lead to a game with that score)。如果有多条边，必须以升序输出，并且以一个空格分隔。
样例输入
4 t -7 t 4 x 2 x 5
样例输出
33 1 2
解题思路
使用一个二维数组 arr[i][j] 存储从 i 到 j 的顶点，若按照规则最终成为一个顶点时，得分的最大值。边缘状态是 arr[i][i] 和 arr[i][i+1], 状态转移是 max { arr[i][k] + arr[k+1][j] } 或者 max { arr[i][k] * arr[k+1][j] }, k∈[i, j), 这取决于那条边是想用乘法还是用加法。最后我们需要从 arr[i][i-1]（可认为是 arr[i][i+n]）获得最大值，然后再扫一遍它们，确定相应的边即可。
嗯嗯，其实我一开始就是这样想才 WA 的……上面的话不全错，也不全对。
因为题目中涉及了乘号，所以，两个负数可以乘出正数来。所以我们还需要一个数组同时记录阶段最小值，这样状态转移就变得复杂了，这也是这道题难的地方。非常阴险的题目哈。
这题给我的一个教训是，递推有时或许好查错，记忆化递归或许有些难，而且容易 TLE. 还有就是有时需要记一些最差解……差极必优。
源代码
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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | import java.util.*; public final class Main { static final class Polygon { private int [] vertices; private char[] edges; private int [][] solution; private int [][] noitulos; private int vertex_count; private static final int neginf = -999999999; private static final int posinf = 999999999; private int calcScore(int edgePos) { if (getEdge(edgePos) == 't') return getVertex(edgePos - 1) + getVertex(edgePos); else return getVertex(edgePos - 1) * getVertex(edgePos); } private int calcScore(int edgePos, int value1, int value2) { if (getEdge(edgePos) == 't') return value1 + value2; else return value1 * value2; } private int larger(int a, int b) { return a > b ? a : b; } private int smaller(int a, int b) { return a < b ? a : b; } void calcSolution() { for (int i = 0; i < vertex_count; ++i) { solution[i][i] = vertices[i]; noitulos[i][i] = vertices[i]; } for (int i = 0; i < vertex_count; ++i) { setSolution(i - 1, i, calcScore(i)); setNoitulos(i - 1, i, calcScore(i)); } for (int k = 2; k < vertex_count; ++k) { for (int i = 0; i < vertex_count; ++i) { int max = neginf, min = posinf; for (int j = i; j < i + k; ++j) { max = larger(max, calcScore(j + 1, getSolution(i, j), getSolution(j + 1, i + k))); max = larger(max, calcScore(j + 1, getNoitulos(i, j), getNoitulos(j + 1, i + k))); min = smaller(min, calcScore(j + 1, getNoitulos(i, j), getNoitulos(j + 1, i + k))); min = smaller(min, calcScore(j + 1, getSolution(i, j), getNoitulos(j + 1, i + k))); min = smaller(min, calcScore(j + 1, getNoitulos(i, j), getSolution(j + 1, i + k))); } setSolution(i, i + k, max); setNoitulos(i, i + k, min); } } } Polygon(int n) { vertex_count = n; vertices = new int [n]; edges = new char[n]; solution = new int [n][n]; noitulos = new int [n][n]; } void setEdge(int id, char oper) { edges[(id + vertex_count) % vertex_count] = oper; } char getEdge(int id) { return edges[(id + vertex_count) % vertex_count]; } void setVertex(int id, int value) { vertices[(id + vertex_count) % vertex_count] = value; } int getVertex(int id) { return vertices[(id + vertex_count) % vertex_count]; } private void setSolution(int start, int end, int score) { solution[(start + vertex_count) % vertex_count] [( end + vertex_count) % vertex_count] = score; } int getSolution(int start, int end) { return solution[(start + vertex_count) % vertex_count] [( end + vertex_count) % vertex_count]; } private void setNoitulos(int start, int end, int score) { noitulos[(start + vertex_count) % vertex_count] [( end + vertex_count) % vertex_count] = score; } int getNoitulos(int start, int end) { return noitulos[(start + vertex_count) % vertex_count] [( end + vertex_count) % vertex_count]; } } public static void main(String[] args) { // Read the polygon. Scanner cin = new Scanner(System.in); int n = cin.nextInt(); Polygon polygon = new Polygon(n); for (int i = 0; i < n; ++i) { polygon.setEdge(i, cin.next().charAt(0)); polygon.setVertex(i, cin.nextInt()); } // Calculate solution. polygon.calcSolution(); // Get max score. int max_score = Polygon.neginf; for (int i = 0; i < n; ++i) { int score = polygon.getSolution(i + 1, i); if (score > max_score) max_score = score; } System.out.println(max_score); // Output edges that removed first to make max score. boolean first_flag = true; if (max_score == polygon.getSolution(0, n - 1)) { System.out.print(1); first_flag = false; } for (int i = 1; i < n; ++i) { if (max_score == polygon.getSolution(i, i - 1)) { if (!first_flag) System.out.print(' '); first_flag = false; System.out.print(i + 1); } } System.out.println(); // Print last line feed. } } |
原创文章，转载请注明来源：http://euyuil.com/2353/poj-1179-polygon/
If I want to review NOIp,I can come here to learn your articles.
但是你又不喜欢呀~