AOJ 2166 - Erratic Sleep Habits

問題概要

T日の睡眠サイクルがある。これはi日目に深夜12時からt_i時間睡眠を取ることを意味する。N個の組が与えられ、各組ではD_i日目にM時から仕事が始まることを意味する。
睡眠サイクルは、1日に1つ進み、T+1日目には1日目に戻る。また、カフェインを摂取することで1日目に戻すことができる。このとき、全ての仕事をこなすためのカフェインの摂取の最小値を出力せよ。

制約

• 1 ≤ T ≤ 30
• 1 ≤ N ≤ 100
• 1 ≤ D_i ≤ 100
• 1 ≤ M_i ≤ 23

解法

DPする。
dp[何日目][サイクルのどの位置] := 最小のカフェイン摂取回数。
なお、D_iは全て異なるとは限らないのでD_iが同じものはその中のM_iが小さいものをi日目の候補とする。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_T 30
#define MAX_N 100
#define INF 1e9
 
int N,T,dp[MAX_N+1][MAX_T];
int arr[MAX_N],t[MAX_T],d;
 
int solve(int idx,int pos){
  if(idx == d+1) return 0;
  if(dp[idx][pos] != -1){
    return dp[idx][pos];
  }
  int res = INF;
  for(int i = 0 ; i < T ; i++){
    if(t[pos] <= arr[idx]){
      res = min(res,solve(idx+1,(pos+1)%T));
    }
    res = min(res,solve(idx+1,1)+1);
  }
  return dp[idx][pos] = res;
}
 
int main(){
  while(cin >> T, T){
    for(int i = 0 ; i < MAX_N ; i++){
      arr[i] = INF;
    }
    for(int i = 0 ; i < T ; i++){
      cin >> t[i];
    }
    int D,M;
    d = 0;
    cin >> N;
    for(int i = 0 ; i < N ; i++){
      cin >> D >> M; D--;
      d = max(d,D);
      arr[D] = min(arr[D],M);
    }
    memset(dp,-1,sizeof(dp));  
    cout << solve(0,0) << endl;
  }
  return 0;
}