Div2 - 250 PikachuEasy
Div1 - 1000 #
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 #
No comments:
Post a Comment