I - I Hate Any Examinations! | 全完早解きコンテスト

$dp[i][j][k]=i$ 時間目にモチベーションが $j$ 、現実逃避度が $k$ になるように行動したときの達成しうる勉強量の最大値
とします。また、そのような状況になるような行動が存在しない場合は $-\infty$ とします。
いま求めたい量は

\max_j\max_kdp[H][j][k]

です。

便宜上勉強をリフレッシュ $0$ とし、 $m_0=-D_M,a_0=-D_A$ とします。
そして、勉強量増加量

f(x)=\left\{\begin{aligned}&1\quad&(x=0)\\&0&(x\ne0)\end{aligned}\right.

を定めます。

明らかに、 $P<k$ となる場合はそこからすべて勉強する方がいいので $k\le P$ を仮定します。
そうすると、このdpは初期値を

dp[0][j][k]=\left\{\begin{aligned}&0&&(j=k=0)\\&-\infty&&(\lnot\ (j=k=0))\end{aligned}\right.

として、遷移は以下のように書くことができます。

$\text{lower}(n)=\max(n,0),\text{mid}(n)=\min(\text{lower}(n),10^2)$ とする。（それぞれ、下限 $0$ 、下限 $0$ 上限 $10^2$ に丸める関数）
各 $x$ について、 $j^\prime=\text{mid}(j+m_x),k^\prime=\text{lower}(k+a_x)$ として $dp[i+1][j^\prime][k^\prime]\leftarrow\max(dp[i+1][j^\prime][k^\prime],dp[i][j][k]+k^\prime f(x))$

以上を適切に実装することで、モチベーションの最大値を $M=10^2$ として、 $O(HMNP)$ でこの問題を解くことができました。

実装例（C++）

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#include <bits/stdc++.h>
using namespace std;
void chmax(int& l, int r) { l = max(l, r); }
int main()
{
  int N, P, H, DM, DA;
  cin >> N >> P >> H;
  cin >> DM >> DA;

  vector<pair<int, int>> refresh(N + 1);
  refresh[0] = {-DM, -DA};
  for (int i = 1; i <= N; i++)
    cin >> refresh[i].first >> refresh[i].second;

  vector<vector<int>> dp(101, vector<int>(P + 1, -1e9));
  dp[0][0] = 0;
  for (int h = 0; h < H; h++)
  {
    vector<vector<int>> nxt = dp;
    for (int m = 0; m <= 100; m++)
      for (int a = 0; a <= P; a++)
        for (int i = 0; i <= N; i++)
          if (a + refresh[i].second <= P)
          {
            int nm = min(100, max(0, m + refresh[i].first));
            int na = max(0, a + refresh[i].second);
            chmax(nxt[nm][na], dp[m][a] + (i == 0 ? nm : 0));
          }
    swap(dp, nxt);
  }

  int ans = 0;
  for (int m = 0; m <= 100; m++)
    for (int a = 0; a <= P; a++)
      chmax(ans, dp[m][a]);

  cout << ans << endl;
}

外部サイトへ移動します

I - I Hate Any Examinations!

実装例（C++）

ユーザー解説