招行信用卡 ac

区间dp，以运算符号为分割做区间dp，比如k为运算符号，即max(i,j) = max(i,k-1) + max(k+1,j);
这里面乘法和除法没有详细推导，直接对4种情况求max和min

     public static void main(String[] args) throws Exception {

     String s = sc.nextLine();
     String[] split = s.split(" ");
     int n = split.length;
     f = new Integer[n][n];
     g = new Integer[n][n];
     System.out.println(min(split, 0, n - 1));
     System.out.println(max(split, 0, n - 1));
 }

 static int max(String[] s, int i, int j) {
     if (f[i][j] != null) {
         return f[i][j];
     }
     f[i][j] = Integer.MIN_VALUE;
     if (j == i) {
         f[i][j] = Integer.valueOf(s[i]);
     } else {

         for (int k = i; k <= j; k++) {
             if ("+".equals(s[k])) {
                 f[i][j] = Math.max(f[i][j], max(s, i, k - 1) + max(s, k + 1, j));
             } else if ("-".equals(s[k])) {
                 f[i][j] = Math.max(f[i][j], max(s, i, k - 1) - min(s, k + 1, j));

             }else if ("*".equals(s[k])) {
                 int a = Math.max(min(s,i,k-1)*min(s,k+1,j),min(s,i,k-1)*max(s,k+1,j));
                 a = Math.max(a, Math.max(max(s,i,k-1)*min(s,k+1,j),max(s,i,k-1)*max(s,k+1,j)));
                 f[i][j] = Math.max(f[i][j], a);
             }else if ("/".equals(s[k])) {
                 int a = Math.max(min(s,i,k-1)/min(s,k+1,j),min(s,i,k-1)/max(s,k+1,j));
                 a = Math.max(a, Math.min(max(s,i,k-1)/min(s,k+1,j),max(s,i,k-1)/max(s,k+1,j)));
                 f[i][j] = Math.max(f[i][j], a);
             }
         }
     }
     return f[i][j];

 }

 static int min(String[] s, int i, int j) {
     if (g[i][j] != null) {
         return g[i][j];
     }
     g[i][j] = Integer.MAX_VALUE;
     if (j == i) {
         g[i][j] = Integer.valueOf(s[i]);
     } else {

         for (int k = i; k <= j; k++) {
             if ("+".equals(s[k])) {
                 g[i][j] = Math.min(g[i][j], min(s, i, k - 1) + min(s, k + 1, j));
             } else if ("-".equals(s[k])) {
                 g[i][j] = Math.min(g[i][j], min(s, i, k - 1) - max(s, k + 1, j));

             }else if ("*".equals(s[k])) {
                 int a = Math.min(min(s,i,k-1)*min(s,k+1,j),min(s,i,k-1)*max(s,k+1,j));
                 a = Math.min(a, Math.max(max(s,i,k-1)*min(s,k+1,j),max(s,i,k-1)*max(s,k+1,j)));
                 g[i][j] = Math.min(g[i][j], a);
             }else if ("/".equals(s[k])) {
                 int a = Math.min(min(s,i,k-1)/min(s,k+1,j),min(s,i,k-1)/max(s,k+1,j));
                 a = Math.min(a, Math.min(max(s,i,k-1)/min(s,k+1,j),max(s,i,k-1)/max(s,k+1,j)));
                 g[i][j] = Math.min(g[i][j], a);
             }
         }
     }
     return g[i][j];

 }

首先pop是肯定不会有新序列出现的，因此可以考虑用字典树遍历的方法。

class Node{
 Map<Integer, Node> child = new HashMap<>();
 Node p;
}
static void func2() {
     Scanner sc = new Scanner(System.in);
     int n = Integer.parseInt(sc.nextLine());
     Node head = new Node();
     Node cur = head;
     int ans = 0;
     for (int i = 0; i < n; i++) {
         String s = sc.nextLine();
         String[] split = s.split(" ");
         if ("pop".equals(split[0]) && cur != head) {
             cur = cur.p;
         } else if ("push".equals(split[0])) {
             int next = Integer.parseInt(split[1]);
             Node nnode = cur.child.get(next);
             if (nnode == null) {
                 ans++;
                 nnode = new Node();
                 nnode.p = cur;
                 cur.child.put(next, nnode);
             }
             cur = nnode;
         }

     }
     System.out.println(ans);
 }