ICPC 2016 国内予選 参加記
Hutari. というチームで出場した。結果は4完で38位。
うちのチームは問題を分担せずにAから順番に解いていく方針をとった。
問題↓
http://icpcsec.storage.googleapis.com/icpc2016-domestic/problems/all_ja.html
A
ソートして隣同士を全部見ていく。
B
適当に数をカウントしていく。
C
mからエラトステネスの篩をする。
バグらせて時間を持っていかれた。しかも1WAでペナルティ。
D
区間DP。twitterを見る限り2回に分けてDPをした人が多いっぽい。僕は1回のDPで解く解法をとった。
dp[l][r] = [l, r]で取り除ける最大のブロック数 とすると、ある区間[l, r]について
abs(w[l] - w[r]) <= 1 かつ [l+1, r-1]のブロックが全て取り除ける(dp[l+1][r-1] = r - l -1)とき、[l, r]のブロックは全て取り除けるのでdp[l][r] = r - l + 1。
そうでないとき、l<=i<=rなiについて[l, i]と[i+1, r]の2つの区間に分割して和をとった値の最大値となるので、dp[l][r] = max(dp[l][i] + dp[i+1][r])。
最終的に求めるべき答えはdp[0][n-1]。
import java.util.*; public class D { static final Scanner in = new Scanner(System.in); static int[][] dp; static int[] w; static int n; static int rec(int l , int r) { if (dp[l][r] != -1) return dp[l][r]; if (l+1 == r) { if (Math.abs(w[l] - w[r]) <= 1) return 2; else return 0; } if (l >= r) { return 0; } if (Math.abs(w[l] - w[r]) <= 1) { int len = rec(l+1, r-1); if (len == r - l -1) { return dp[l][r] = r - l + 1; } } int res = 0; for (int i=l; i<r; i++) { res = Math.max(res, rec(l, i) + rec(i+1, r)); } return dp[l][r] = res; } static boolean solve() { n = in.nextInt(); if (n == 0) return false; w = new int[n]; for (int i=0; i<n; i++) { w[i] = in.nextInt(); } dp = new int[n][n]; for (int i=0; i<n; i++) { Arrays.fill(dp[i], -1); } System.out.println(rec(0, n-1)); return true; } public static void main(String[] args) { while(solve()); in.close(); } }
緊張した〜...。