AOJ2166 Erratic Sleep Habits

問題リンク Erratic Sleep Habits

• 概要

長さTの起床時間tiのサイクルとN個の仕事リストが与えられる。仕事はDi日にMi時から始まる。Di日にMi時以前に起きればこの仕事をすることができる(ti <= Mi)。
薬を飲むことで起床時間のサイクルを強制的に最初に戻すことができる。
全ての仕事をこなすために必要な薬の摂取回数の最小値を求めよ。
なお、起床時間のサイクルの1番目は必ず1である。
1 <= T <= 30
1 <= ti <= 23
1 <= N <= 100
1 <= Di <= 100
1 <= Mi <= 23

• 解法

DPです。
dp[i][j]: i日目にサイクルj番目だったときの、残りの仕事をこなすための薬の最小摂取回数
という表を埋めれば解けます。forループでもメモ化再帰でも好きな方でいいんではないでしょうか。
入力中にD日目の仕事が無い場合、D日目の仕事は23(or 23以上)時に入っていると考えると変な場合分けでごちゃごちゃせずに済むと思います。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Erratic Sleep Habits
public class AOJ2166 {

	int T, n, INF = 1<<29;
	int[] a, d;
	int[][] dp;
	
	int get(int k, int c){
		if(k==101)return 0;
		if(dp[k][c]!=-1)return dp[k][c];
		int res = get(k+1, 0)+1;
		int f = k+1, nc = (c+1)%T;
		for(;f<=100;f++, nc=(nc+1)%T){
			if(d[f]<a[nc])break;
			res = Math.min(res, get(f+1, 0)+1);
		}
		if(100<f)res = 0;
		return dp[k][c] = res;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			T = sc.nextInt();
			if(T==0)break;
			a = new int[T];
			for(int i=0;i<T;i++)a[i]=sc.nextInt();
			n = sc.nextInt();
			d = new int[101];
			Arrays.fill(d, INF);
			for(int i=0;i<n;i++){
				int x = sc.nextInt();
				d[x] = Math.min(d[x], sc.nextInt());
			}
			dp = new int[101][T];
			for(int[]p:dp)Arrays.fill(p, -1);
			System.out.println(get(1, 0));
		}
	}
	
	public static void main(String[] args) {
		new AOJ2166().run();
	}
}