Codeforces Round #303 Div2 C: Woodcutters (動的計画法)

問題

codeforces.com

解法

i+1番目の木にとっては、i番目の木が左側に倒れているか否かが分かれば良いので、渡すDPを書く。

コード

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] x = new int[N];
		int[] h = new int[N];
		for (int i = 0; i < N; i++) {
			x[i] = sc.nextInt();
			h[i] = sc.nextInt();
		}
		sc.close();

		int[][] dp = new int[N][2];
		// dp[i][0]:= 左に倒すor倒さない
		// dp[i][1]:= 右に倒す
		dp[0][0] = 1;
		for (int i = 0; i < N - 1; i++) {
			dp[i + 1][0] = Math.max(dp[i][0], dp[i][1]);
			if (x[i + 1] - h[i + 1] > x[i] + h[i]) {
				dp[i + 1][0] = Math.max(Math.max(dp[i][0] + 1, dp[i][1] + 1), dp[i + 1][0]);
			}
			if (x[i + 1] - h[i + 1] > x[i]) {
				dp[i + 1][0] = Math.max(dp[i][0] + 1, dp[i + 1][0]);
			}
			if (i + 2 == N || x[i + 1] + h[i + 1] < x[i + 2]) {
				dp[i + 1][1] = Math.max(dp[i + 1][1], Math.max(dp[i][0] + 1, dp[i][1] + 1));
			}
		}
		System.out.println(Math.max(dp[N - 1][0], dp[N - 1][1]));

	}
}