競プロやります。

競プロを頑張るブログです。

Educational DP Contest / DP まとめコンテスト (A - E)

A - Frog 1

https://atcoder.jp/contests/dp/tasks/dp_a

方針

足場 1 から出発し、足場 i に辿り着くのに必要な最小のコストを  dp[i] とします。求めたいものは  dp[N] です。

はじめ足場 1 にいるので、 dp[1] = 0 。また足場 2 へ行くためには足場 1 ⇒ 2 とジャンプするしかないので、 dp[2] = |h_2 - h_1| です。
 i > 2 のとき、足場 i へたどり着くためには、(1) 足場 i - 1 から足場 i へジャンプする、または (2) 足場 i - 2 から足場 i へジャンプする、の2通りの方法があります。(足場 i -2 ⇒ i - 1 ⇒ i と辿る経路は(1)に含まれます)

  • (1) のとき
    • 足場 i - 1 へ行くための最小コストは  dp[i-1]、ジャンプのコストが  |h_i - h_{i-1}|で、この経路での最小コストは合わせて  dp[i-1] + |h_i - h_{i-1}| です。
  • (2) のとき
    • (1)と全く同様に考えて、最小コストは  dp[i-2] + |h_i - h_{i-2}| です。

足場 i へたどり着く2通りの方法についての各々の最小コストが分かったので、 dp[i] はそれらの小さい方となります。すなわち、
   dp[i] = \min\{ dp[i-1] + |h_i - h_{i-1}|,~dp[i-2] + |h_i - h_{i-2}| \}
です。 dp[0], dp[1] が分かっているので、この漸化式を用いて順番に  dp[3], dp[4], \dots と求めていけば、計算量  O(N) dp[N] が求まります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;  cin >> N;
    vector<int> h(N+1);
    for(int i=1; i<=N; i++) cin >> h[i];

    vector<int> dp(N+1);
    dp[1] = 0;
    dp[2] = abs(h[2]-h[1]);
    for(int i=3; i<=N; i++){
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
    }
    cout << dp[N] << endl;
}

B - Frog 2

https://atcoder.jp/contests/dp/tasks/dp_b
カエルの飛び越せる足場の数が一般化されました。

方針

足場 1 から出発し、足場 i に辿り着くのに必要な最小のコストを  dp[i] とします。求めたいものは  dp[N] です。

足場 i - j から足場 i へ直接ジャンプするとき、足場 i までの最小コストは  dp[i-j] + |h_i - h_{i-j}| と書けます。ここで、j は 1 から K の値をとれますが、足場 1 より前の足場は無いので、 i - j \geq 1 より、  j \leq i-1 です。これと j が 1 以上 K 以下であることをあわせて、 1 \leq j \leq \min(K, i-1) です。

j がこの範囲を動くときの  dp[i-j] + |h_i - h_{i-j}| の最小値が  dp[i] となります。すなわち、
   dp[i] = \min\{ dp[i-j] + |h_i - h_{i-j}| \}_{1 \leq j \leq \min(K, i-1)}
です。各  dp[i] を計算するのに足場を最大 K だけ遡って見るので、計算量は  O(NK) となります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, K;  cin >> N >> K;
    vector<int> h(N+1);
    for(int i=1; i<=N; i++) cin >> h[i];

    vector<int> dp(N+1);
    dp[1] = 0;
    for(int i=2; i<=N; i++) dp[i] = 1e9;

    for(int i=2; i<=N; i++){
        for(int j=1; j<=min(K,i-1); j++){
            dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]));
        }
    }
    cout << dp[N] << endl;
}

C - Vacation

https://atcoder.jp/contests/dp/tasks/dp_c

方針

太郎君の活動が A, B, C とありますが、扱いづらいのでそれぞれ 0, 1, 2 とし、i 日目に活動 j をしたときに得る幸福度を  h_{i, j} とします。また、 i 日目に活動 j をした時点での幸福度の総和の最大値を  dp[i][j] とします。求めるものは  dp[N][0],~dp[N][1],~dp[N][2] の中の最大値です。

まず1日目は何の制約も無くどの活動も選べるので、 dp[1][j] = h_{1,j} となります。
次に i > 1 として i 日目を考えます。

  • (例) i 日目に活動 0 を選ぶとき
    • 前日の活動は 1, 2 のどちらかですから、 dp[i][0] = \max\{ dp[i-1][1],~dp[i-1][2] \} + h_{i, 0} です。

i 日目に他の活動を選ぶ場合も全く同様に考えられるので、合わせて以下のように書けます:
   dp[i][j] = \max\{ dp[i-1][k] \}_{k \neq j} + h_{i,j}

あとはこの漸化式を用いて  dp[N][0],~dp[N][1],~dp[N][2] を求め、その中の最大値を出力すればよいです。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;  cin >> N;
    vector<vector<int>> h;
    h = vector<vector<int>>(N+1, vector<int>(3, 0));
    for(int i=1; i<=N; i++) cin >> h[i][0] >> h[i][1] >> h[i][2];
    
    vector<vector<int>> dp;
    dp = vector<vector<int>>(N+1, vector<int>(3, 0));
    for(int i=1; i<=N; i++){
        for(int j=0; j<3; j++){
            for(int k=0; k<3; k++){
                if(j != k){
                    dp[i][j] = max(dp[i][j], dp[i-1][k] + h[i][j]);
                }
            }
        }
    }

    int ans = 0;
    for(int i=0; i<3; i++) ans = max(ans, dp[N][i]);
    cout << ans << endl;
}

D - Knapsack 1

https://atcoder.jp/contests/dp/tasks/dp_d

方針

品物 1, 2, ......, i の中から重さがピッタリ j になるように品物を選んだ時の、価値の総和の最大値を  dp[i][j] とします。求めるものは  dp[N][0],~dp[N][1], \dots,~dp[N][W] の中の最大値です。

まず i = 1 のとき、品物を重さを j になるように選べるのは、 j = w1 のときだけですから、
   dp[1][j] = \begin{cases}
                               v_1 & (j = w_1) \\
                               0 &(j \neq w_1)
\end{cases}
です。

次に i > 1 として、品物 1, 2, ......, i から選ぶことを考えます。重さ j の値によって場合分けします。

  •  j < w_i のとき
    • ナップサックの重さをぴったり j にしたいので、重さ  w_i の品物を入れることは出来ません。したがって、価値の総和の最大値は品物 i - 1 までの中から重さ j にするときと同じです。 dp[i][j] = dp[i-1][j] となります。
  •  j \geq w_i のとき
    • このときはナップサックに品物 i を入れることが出来ますが、もちろん入れないこともできるので、両方の場合を考えます。以下より、 dp[i][j] = \max\{ dp[i-1][j],~dp[i-1][j-w_i] + v_i \} です。
      • 品物 i を入れないとき、 dp[i][j] = dp[i-1][j]
      • 品物 i を入れるときは、品物 i - 1 までで重さをぴったり  j - w_i としなければいけないので、 dp[i][j] = dp[i-1][j-w_i] + v_i

以上まとめると、漸化式は次のようになり、計算量は  O(NW) です。
   dp[i][j] = \begin{cases}
                    dp[i-1][j] &(j < w_i ) \\
                    \max\{ dp[i-1][j],~dp[i-1][j-w_i] + v_i \} &( j \geq w_i)
\end{cases}

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll N, W;  cin >> N >> W;
    vector<ll> w(N+1), v(N+1);
    for(int i=1; i<=N; i++) cin >> w[i] >> v[i];

    vector<vector<ll>> dp;
    dp = vector<vector<ll>>(N+1, vector<ll>(W+1, 0));
    dp[1][w[1]] = v[1];

    for(int i=2; i<=N; i++){
        for(int j=0; j<=W; j++){
            if(w[i] <= j){
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    ll ans = 0;
    for(int i=0; i<=W; i++) ans = max(ans, dp[N][i]);
    cout << ans << endl;
}

E - Knapsack 2

https://atcoder.jp/contests/dp/tasks/dp_e

方針

D 問題と同じ方法で解こうとすると、計算量が  O(NW) なので間に合いません。そこで、品物 1, 2, ......, i から価値がピッタリ j になるように選んだ時の、重さの総和の最小値を  dp[i][j] とします。求めるものは  dp[N][j] \leq W となる j の中の最大値です。なお、品物 1, 2, ......, i から価値をぴったり j にすることが出来ない場合は、 dp[i][j] = \text{inf} とします。ここで inf は全ての品物の重さの総和よりも大きな値です。

まず i = 1 のとき、価値をピッタリ j にできるのは j = 0, v1 のときだけですから、
   dp[1][j] = \begin{cases}
                               0 & (j = 0) \\
                               w_1 & (j = v_1) \\
                               \text{inf} &(j \neq 0,~v_1)
\end{cases}

次に i > 1 のときです。

  •  j < v_i のとき
    • ナップサックの品物の価値の総和をピッタリ j としたいので、品物 i を入れることは出来ません。したがって、重さの総和の最小値は品物 i - 1 までの中から価値 j にするときと同じです。 dp[i][j] = dp[i-1][j] となります。
  •  j \geq v_i のとき
    • ナップサックに品物 i を入れることが出来ますが、もちろん入れないこともできるので、両方の場合を考えます。以下より、 dp[i][j] = \min\{ dp[i-1][j],~dp[i-1][j-v_i] + w_i \} です。
      • 品物 i を入れないとき、 dp[i][j] = dp[i-1][j]
      • 品物 i を入れるときは、品物 i - 1 までで価値をぴったり  j - v_i としなければいけないので、 dp[i][j] = dp[i-1][j-v_i] + w_i

以上まとめると、漸化式は次のようになり、計算量は  O(NV) です。ここで  V は全ての品物の価値の総和です。
   dp[i][j] = \begin{cases}
                    dp[i-1][j] &(j < v_i ) \\
                    \min\{ dp[i-1][j],~dp[i-1][j-v_i] + w_i \} &( j \geq v_i)
\end{cases}

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll N, W;  cin >> N >> W;
    vector<ll> w(N+1), v(N+1);
    ll Vsum = 0;
    for(int i=1; i<=N; i++){ 
        cin >> w[i] >> v[i];
        Vsum += v[i];
    }

    ll inf = 1e15;
    vector<vector<ll>> dp;
    dp = vector<vector<ll>>(N+1, vector<ll>(Vsum+1, inf));
    dp[1][0] = 0;
    dp[1][v[1]] = w[1];

    for(int i=2; i<=N; i++){
        for(int j=0; j<=Vsum; j++){
            if(v[i] <= j){
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    for(int i=Vsum; i>=0; i--){
        if(dp[N][i] <= W){
            cout << i << endl;
            return 0;
        }
    }
}