ACM-ICPC 模擬国内予選 2013 D: 沈みゆく島 [Licence: NYSL Version 0.9982]

Main.java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    private static final char[] nums = "0123456789".toCharArray();
    private static final char[] opes = "+-*&^|".toCharArray();
    private static final Map<String, Long> cache = new HashMap<>();

    public static void main(String... args) {
        try (final Scanner sc = new Scanner(System.in)) {
            while (sc.hasNext()) {
                final int N = sc.nextInt();
                if (N == 0)
                    return;
                final String s = sc.next();
                final long ans = memoize(2 - (N & 1), s, 1);
                System.out.println(ans);
                cache.clear();
            }
        }
    }

    private static long memoize(final int N, final String s, final int sgn) {
        if (cache.containsKey(s))
            return cache.get(s);

        final long ret = solve(N, s, sgn);
        cache.put(s, ret);
        return ret;
    }

    private static long solve(final int N, final String s, final int sgn) {
        final String t = s.trim();
        final long v = evaluate(t);

        if (v == -Long.MAX_VALUE)
            return Long.MAX_VALUE;

        if (N == 0)
            return sgn * v;

        final int l = t.length();
        long max = -Long.MAX_VALUE;
        // insert
        for (int i = 0; i <= l; i++) {
            for (final char c : nums)
                max = Math.max(max, -memoize(N - 1, new StringBuilder(s).insert(i, c).toString(), -sgn));
            for (final char c : opes)
                max = Math.max(max, -memoize(N - 1, new StringBuilder(s).insert(i, c).toString(), -sgn));
        }
        // remove
        for (int i = 0; i < l; i++)
            if (s.charAt(i) != '(' && s.charAt(i) != ')')
                max = Math.max(max, -memoize(N - 1, s.substring(0, i) + s.substring(i + 1) + "  ", -sgn));

        return max;
    }

    private static long evaluate(final String s) {
        return new Evaluator(s).evaluate();
    }

    private static void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }
}