Educational DP Contest / DP まとめコンテスト (A - E)
A - Frog 1
https://atcoder.jp/contests/dp/tasks/dp_a
方針
足場 1 から出発し、足場 i に辿り着くのに必要な最小のコストを とします。求めたいものは です。
はじめ足場 1 にいるので、 。また足場 2 へ行くためには足場 1 ⇒ 2 とジャンプするしかないので、 です。
のとき、足場 i へたどり着くためには、(1) 足場 i - 1 から足場 i へジャンプする、または (2) 足場 i - 2 から足場 i へジャンプする、の2通りの方法があります。(足場 i -2 ⇒ i - 1 ⇒ i と辿る経路は(1)に含まれます)
- (1) のとき
- 足場 i - 1 へ行くための最小コストは 、ジャンプのコストが で、この経路での最小コストは合わせて です。
- (2) のとき
- (1)と全く同様に考えて、最小コストは です。
足場 i へたどり着く2通りの方法についての各々の最小コストが分かったので、 はそれらの小さい方となります。すなわち、
です。 が分かっているので、この漸化式を用いて順番に と求めていけば、計算量 で が求まります。
ソースコード
#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 に辿り着くのに必要な最小のコストを とします。求めたいものは です。
足場 i - j から足場 i へ直接ジャンプするとき、足場 i までの最小コストは と書けます。ここで、j は 1 から K の値をとれますが、足場 1 より前の足場は無いので、 より、 です。これと j が 1 以上 K 以下であることをあわせて、 です。
j がこの範囲を動くときの の最小値が となります。すなわち、
です。各 を計算するのに足場を最大 K だけ遡って見るので、計算量は となります。
ソースコード
#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 をしたときに得る幸福度を とします。また、 i 日目に活動 j をした時点での幸福度の総和の最大値を とします。求めるものは の中の最大値です。
まず1日目は何の制約も無くどの活動も選べるので、 となります。
次に i > 1 として i 日目を考えます。
- (例) i 日目に活動 0 を選ぶとき
- 前日の活動は 1, 2 のどちらかですから、 です。
i 日目に他の活動を選ぶ場合も全く同様に考えられるので、合わせて以下のように書けます:
あとはこの漸化式を用いて を求め、その中の最大値を出力すればよいです。
ソースコード
#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 になるように品物を選んだ時の、価値の総和の最大値を とします。求めるものは の中の最大値です。
まず i = 1 のとき、品物を重さを j になるように選べるのは、 j = w1 のときだけですから、
です。
次に i > 1 として、品物 1, 2, ......, i から選ぶことを考えます。重さ j の値によって場合分けします。
- のとき
- ナップサックの重さをぴったり j にしたいので、重さ の品物を入れることは出来ません。したがって、価値の総和の最大値は品物 i - 1 までの中から重さ j にするときと同じです。 となります。
- のとき
- このときはナップサックに品物 i を入れることが出来ますが、もちろん入れないこともできるので、両方の場合を考えます。以下より、 です。
- 品物 i を入れないとき、 。
- 品物 i を入れるときは、品物 i - 1 までで重さをぴったり としなければいけないので、 。
- このときはナップサックに品物 i を入れることが出来ますが、もちろん入れないこともできるので、両方の場合を考えます。以下より、 です。
以上まとめると、漸化式は次のようになり、計算量は です。
ソースコード
#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 問題と同じ方法で解こうとすると、計算量が なので間に合いません。そこで、品物 1, 2, ......, i から価値がピッタリ j になるように選んだ時の、重さの総和の最小値を とします。求めるものは となる j の中の最大値です。なお、品物 1, 2, ......, i から価値をぴったり j にすることが出来ない場合は、 とします。ここで inf は全ての品物の重さの総和よりも大きな値です。
まず i = 1 のとき、価値をピッタリ j にできるのは j = 0, v1 のときだけですから、
次に i > 1 のときです。
- のとき
- ナップサックの品物の価値の総和をピッタリ j としたいので、品物 i を入れることは出来ません。したがって、重さの総和の最小値は品物 i - 1 までの中から価値 j にするときと同じです。 となります。
- のとき
- ナップサックに品物 i を入れることが出来ますが、もちろん入れないこともできるので、両方の場合を考えます。以下より、 です。
- 品物 i を入れないとき、 。
- 品物 i を入れるときは、品物 i - 1 までで価値をぴったり としなければいけないので、 。
- ナップサックに品物 i を入れることが出来ますが、もちろん入れないこともできるので、両方の場合を考えます。以下より、 です。
以上まとめると、漸化式は次のようになり、計算量は です。ここで は全ての品物の価値の総和です。
ソースコード
#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; } } }