AOJ 2166: Erratic Sleep Habits
問題
Erratic Sleep Habits | Aizu Online Judge
睡眠のサイクル(12時に寝てt時間寝る)と、D日目はM時に起きないといけない、という情報が与えられるので、睡眠サイクルをリセットする最小回数を求める。
解法
動的計画法。dp[i日目に][サイクルjがきてる]ときの最小回数をメモしておく。
コード
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (true) { int C = sc.nextInt(); if (C == 0) { sc.close(); break; } int[] cycle = new int[C]; for (int i = 0; i < C; i++) { cycle[i] = sc.nextInt(); } int N = sc.nextInt(); int[] meeting = new int[100]; for (int i = 0; i < N; i++) { int day = sc.nextInt(); int meet = sc.nextInt(); if (meeting[day - 1] != 0) { meeting[day - 1] = Math.min(meet, meeting[day - 1]); } else { meeting[day - 1] = meet; } } // dp[i日目に][サイクルjがきてる]ときのカフェイン最小回数 int[][] dp = new int[100][C]; for (int i = 0; i < dp.length; i++) { Arrays.fill(dp[i], 100); } dp[0][0] = 0; for (int i = 0; i < dp.length - 1; i++) { for (int j = 0; j < C; j++) { // 間に合う時 if (cycle[(j + 1) % C] <= meeting[i + 1] || meeting[i + 1] == 0) { dp[i + 1][(j + 1) % C] = Math.min(dp[i][j], dp[i + 1][(j + 1) % C]); } // カフェインを摂取する時 dp[i + 1][0] = Math.min(dp[i][j] + 1, dp[i + 1][0]); } } int caffeine = Integer.MAX_VALUE; for (int i = 0; i < dp[99].length; i++) { caffeine = Math.min(caffeine, dp[99][i]); } System.out.println(caffeine); } } }