競プロ精選 100 問 by C++<動的計画法：ナップザック DP>
はじめに
こんにちは！
今回から、5回連続DPです
34 ALDS_10_A - フィボナッチ数
問題はこちらです！
問題文↓
フィボナッチ数列のN番目を求めてください
再帰関数だとO(N²)だけど、前のデータをmemo化しておくことでDPによってO(N)となる基本問題！
コードはこんな感じになりました
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { vector<int> A = {1, 1}; int n; cin >> n; rep(i, n - 1) { A.push_back(A[i] + A[i + 1]); } cout << A[n] << endl; return 0; }
全てのデータをvectorに保存しなくても良い気もする？
35 DPL_1_B - 0,1ナップザック問題
問題はこちらです！
問題文↓
重さWを超えないようにN個のものから価値が最大になるように選んでください
DPの基本問題でした！
コードはこんな感じです
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { int n, w; cin >> n >> w; vector<pair<int, int>> items(n); rep(i, n) { int weight, value; cin >> value >> weight; items[i] = make_pair(weight, value); } // ナップザックDP vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0)); rep(i, n) { rep(j, w + 1) { if (j - items[i].first >= 0) { dp[i + 1][j] = max(dp[i][j], dp[i][j - items[i].first] + items[i].second); } else { dp[i + 1][j] = dp[i][j]; } } } cout << dp[n][w] << endl; return 0; }
基本問題なのでcopilotがほぼ書いてくれました(よくない)
36 DPL_1_C - ナップザック問題
問題はこちらです！
問題文↓
# 35に要素を追加する ・同じアイテムを何回も選ぶことが出来る
簡単なDPです！
コードはこんな感じ
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { int n, w; cin >> n >> w; vector<pair<int, int>> items(n); rep(i, n) { int weight, value; cin >> value >> weight; items[i] = make_pair(weight, value); } // 同じアイテムも選ぶことが出来るナップザックDP vector<int> dp(w + 1, 0); rep(i, n) { rep(j, w + 1) { if (j - items[i].first >= 0) { dp[j] = max(dp[j], dp[j - items[i].first] + items[i].second); } } } cout << dp[w] << endl; return 0; }
DP練習しなきゃ,,,
37 DPL_1_A - コイン問題
問題はこちらです！
問題文↓
いくつかの額面がバラバラのコインが与えられる それらを組み合わせてn円を作成する そのときの最小のコインの枚数はいくつか 同じコインを使用してもよい
コードはこんな感じ
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { int n, m; cin >> n >> m; vector<int> coins(m); rep(i, m) cin >> coins[i]; // coinでn円を作る最小の枚数のDP vector<int> dp(n + 1, 100000); dp[0] = 0; rep(i, m) { rep(j, n + 1) { if (j - coins[i] >= 0) { dp[j] = min(dp[j], dp[j - coins[i]] + 1); } } } cout << dp[n] << endl; return 0; }
基本問題はcopilotに任せて、コードを理解することに専念します
38 ALDS_10_C - 最長共通部分列
問題はこちらです！
問題文↓
最長共通部分列とは、{x_1,x_2,x_3,...,x_n}と{y_1,y_2,y_3,...,y_m}という文字列があった時、いくつかの文字を取り出して等しくなった文字列のうち、最長の長さのものです
例えば、abcdeはacdという文字列を部分列として持っており、acdfという文字列もacdという部分列を持っています
このacdという文字列を共通部分列ということにします
この共通部分列のうち、最長のものの長さを求めてください
コードはこんな感じ
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i < (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; int smallMOD = 998244353; int bigMOD = 1000000007; int main() { int n; cin >> n; // 最長共通部分列問題をDPで解く rep(i, n) { string x, y; cin >> x >> y; int m = x.size(); int l = y.size(); vector<vector<int>> dp(m + 1, vector<int>(l + 1, 0)); rep(i, m) { rep(j, l) { if (x[i] == y[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; } else { dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]); } } } cout << dp[m][l] << endl; } return 0; }
めっちゃむずい、、、
おわりに
お疲れ様でした！
次は真面目にDPの精進をします
ではまた！
