Codeforces Round #303 Div2 C: Woodcutters (動的計画法)
解法
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])); } }