AOJ2166 Erratic Sleep Habits

Erratic Sleep Habits

Peter is a person with erratic sleep habits. He goes to sleep at twelve o'lock every midnight. He gets up just after one hour of sleep on some days; he may even sleep for twenty-three hours on other days. His sleeping duration changes in a cycle, where he always sleeps for only one hour on the first day of the cycle.

睡眠周期 が与えられる．カフェインを取ることでこの睡眠周期を最初に戻すことが出来るとき，全ての予定をこなせるカフェインの量の最大値を求める．

とした． の場合は のどこからでも (カフェインを取ること)で遷移できて，他の場合は が 日目の一番最初の予定より早ければ， より遷移できる．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  int t;
  while(cin >> t && t) {

      vector<int> v(t);
      rep(i, t) cin >> v[i];

      int n;
      cin >> n;

      vector<int> d(n), m(n);
      int dm[105], day = 0;
      rep(i, 105) dm[i] = INF;

      rep(i, n) {
          cin >> d[i] >> m[i];
          dm[d[i]-1] = min(dm[d[i]-1], m[i]);
          day = max(day, d[i]);
      }

      int dp[105][35];
      rep(i, 105) rep(j, 35) dp[i][j] = INF;

      dp[0][0] = 0;

      REP(i, 1, day) {
          rep(j, t) {
              if(j == 0) {
                  rep(k, t) {
                      dp[i][j] = min(dp[i][j], dp[i-1][k] + 1);
                  }
                  dp[i][j] = min(dp[i][j], dp[i-1][t-1]);
              } else {
                  if(v[j] <= dm[i]) {
                      dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
                  }
              }
          }
      }

      int ans = INF;
      rep(i, t) {
          ans = min(ans, dp[day-1][i]);
      }

      cout << ans << endl;
  }

  return 0;
}
Mar 24th, 2016
300, aoj-icpc, 動的計画法