多边形游戏

标题：	多边形游戏
时限：	1000 ms
内存限制：	10000 K
总时限：	3000 ms
描述：	多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：(1)选择一条边E以及由E连接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。
输入：
输出：
输入样例：	5 10 + -1 x -2 x 3 + -8 x
输出样例：	486
提示：
来源：

动态规划法

  1 import java.util.Scanner;
  2 
  3 public class Main {
  4     static int n = 0;
  5     static int minf = 0;
  6     static int maxf = 0;
  7     static int[][][] m = null;
  8     static int[] v = null;
  9     static String[] op = null;
 10     static int a = 0;
 11 
 12     public static void minMAX(int i, int s, int j) {
 13         int[] e = new int[5];
 14         int a, b, c, d;
 15         a = m[i][s][0];
 16         b = m[i][s][1];
 17         int r = (i + s - 1) % n + 1;
 18         c = m[r][j - s][0];
 19         d = m[r][j - s][1];
 20 
 21         if (op[r].equals("+")) {
 22             minf = a + c;
 23             maxf = b + d;
 24         } else {
 25             e[1] = a * c;
 26             e[2] = a * d;
 27             e[3] = b * c;
 28             e[4] = b * d;
 29 
 30             minf = e[1];
 31             maxf = e[1];
 32 
 33             for (int k = 2; k < 5; k++) {
 34                 if (minf > e[k]) {
 35                     minf = e[k];
 36                 }
 37                 if (maxf < e[k]) {
 38                     maxf = e[k];
 39                 }
 40             }
 41         }
 42 
 43     }
 44 
 45     public static int polyMax() {
 46 
 47         for (int j = 2; j <= n; j++) {
 48             for (int i = 1; i <= n; i++) {
 49                 for (int s = 1; s < j; s++) {
 50                     minMAX(i, s, j);
 51                     if (m[i][j][0] > minf) {
 52                         m[i][j][0] = minf;
 53                     }
 54 
 55                     if (m[i][j][1] < maxf) {
 56                         m[i][j][1] = maxf;
 57                     }
 58                 }
 59             }
 60         }
 61 
 62         int temp = m[1][n][1];
 63 
 64         for (int j = 2; j <= n; j++) {
 65             if (temp < m[j][n][1]) {
 66                 temp = m[j][n][1];
 67             }
 68         }
 69 
 70         return temp;
 71     }
 72 
 73     public static void main(String[] args) {
 74         // TODO Auto-generated method stub
 75 
 76         // System.out.println("请输入定点数：");
 77         Scanner myscanner = new Scanner(System.in);
 78         n = myscanner.nextInt();
 79         myscanner.nextLine();
 80         v = new int[n + 1];
 81         op = new String[n + 1];
 82         m = new int[n + 1][n + 1][2];
 83 
 84         // System.out.println("请输入图信息：");
 85 
 86         String s = myscanner.nextLine();
 87         String[] sr = s.split(" ");
 88         int mv = n, mo = n;
 89         for (int i = 0; i < sr.length; i++) {
 90             if (i % 2 == 0) {
 91                 v[mv] = Integer.parseInt(sr[i]);
 92                 mv--;
 93             } else {
 94                 op[mo] = sr[i];
 95                 mo--;
 96             }
 97         }
 98 
 99         /*
100          * for (int i = 1; i <= n; i++) { System.out.print(v[i] + " "); } for
101          * (int i = 1; i <= n; i++) { System.out.print(op[i] + " "); }
102          */
103 
104         for (int i = 1; i <= n; i++) {
105             m[i][1][0] = v[i];
106             m[i][1][1] = v[i];
107         }
108 
109         a = Main.polyMax();
110         System.out.println(a);
111     }
112 
113 }