SRM 533

Div2 - 250 PikachuEasy

public class PikachuEasy {
   public String check(String word) {
        String w[] = {"pi", "ka", "chu"};
        while (true) {
            boolean was = false;
            for (String cur : w) {
                if (word.startsWith(cur)) {
                    word = word.substring(cur.length());
                    was = true;
                }
            }
            if (!was) break;
        }
        if (word.length() == 0) return "YES";
        return "NO";
   }
}

Div2 - 500, Div1 - 250 CasketOfStarEasy

public class CasketOfStarEasy {
    int w[];
    Integer dp[][] = new Integer[100][100];
    int rec(int lo, int hi) {
        if (lo + 1 == hi) return 0;
        if (dp[lo][hi] != null) return dp[lo][hi];
        int tmp = w[lo] * w[hi];
        int res = 0;
        for (int k = lo + 1; k < hi; ++k) {
            res = Math.max(res, rec(lo, k) + rec(k, hi) + tmp);
        }
        return dp[lo][hi] = res;
    }
    public int maxEnergy(int[] weight) {
        this.w = weight;
        return rec(0, weight.length - 1);
    }
}

Div2 - 1000 MagicalGirl

public class MagicalGirl {
    int[] day, win, gain;
    int M;
    Double dp[][] = new Double[51][100 * 1000 + 1];
    
    double rec(int k, int m) {
        if (dp[k][m] != null) return dp[k][m];
        int curDay = day[k];
        if (m == 0) return curDay;
        int nextDay = k + 1 < day.length ? day[k + 1] : 10000000;
        int d = nextDay - curDay;
        double r1, r2;
        if (m >= d) r1 = rec(k + 1, m - d);
         else r1 = curDay + m;
        int g = Math.min(m + gain[k], M);
        double p = win[k] / 100.0;
        if (g >= d) r2 = rec(k + 1, g - d) * p + curDay * (1.0 - p);
        else r2 = (curDay + g) * p + curDay * (1.0 - p);
        return dp[k][m] = Math.max(r1, r2);
    }

    public double maxExpectation(int M, int[] day, int[] win, int[] gain) {
        int n = day.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (day[i] > day[j]) {
                    int tmp;
                    tmp = day[i]; day[i] = day[j]; day[j] = tmp;
                    tmp = win[i]; win[i] = win[j]; win[j] = tmp;
                    tmp = gain[i]; gain[i] = gain[j]; gain[j] = tmp;
                }
            }
        }
        this.day = day;
        this.win = win;
        this.gain = gain;
        this.M = M;
        if (M < day[0]) return M;
        return rec(0, M - day[0]);
    }
}

Div1 - 500 #

Div1 - 1000 #