Many Go Round [Maximum-Cup 2018 D]

https://beta.atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_d

解法

https://beta.atcoder.jp/contests/maximum-cup-2018/submissions/2312685

動的計画法で解いていく。
正直、どの辺からDPが思いついたのかを聞かれると微妙な所ではあるが、

• 制約でNMが行ける
• 燃料タンクの選び方は2^N通りあり、これをなんとかしたい
• 「X周以内に止まる事ができるか」を「周回の最小回数≦X」と読み替える

この辺から推測した。
　
DPは「dp[i][j] := i番目までの燃料タンクを使って番号jの休憩所に止まるための周回の最小回数」で作る。
これは最初は全てinfで、dp[0][0]が1とする。
あとは、燃料タンクで移動する、移動しないの遷移がそれぞれあるので、それを実装する。
dp[N][L]≦XならばYes,そうでないならNo

int N, M, L, X, A[10101], dp[10101][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> L >> X;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N + 1) rep(j, 0, M) dp[i][j] = inf;
    dp[0][0] = 1;

    rep(i, 0, N) rep(j, 0, M) {
        if (M <= j + A[i]) {
            int x = A[i];
            int d = 0;
            
            d++;
            x -= M - j;

            d += x / M;
            x %= M;

            chmin(dp[i + 1][x], dp[i][j] + d);
        }
        else chmin(dp[i + 1][j + A[i]], dp[i][j]);
        chmin(dp[i + 1][j], dp[i][j]);
    }

    if (dp[N][L] <= X) printf("Yes\n");
    else printf("No\n");
}