C++の練習を兼ねて, Typical DP Contest の 問題A (A – コンテスト) を解いてみた.
■感想.
1. どこかで類題を見た記憶があったので, 探したところ, yukicoder の No.4 おもりと天秤 に似ていることが分かった.
2. DPを使う方法を模索したが, 使い方が, 分からなかったので, 要復習と認識している.
■C++版プログラム(問題A／AC版).
|
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 39 40 41 42 43 44 45 46 47 |
// yukicoder の 問題 を 参照. // No.4 おもりと天秤 // https://yukicoder.me/problems/no/4 #include <bits/stdc++.h> using namespace std; // 獲得可能な得点を更新する. // @param m: 得点のリスト. // @param s: 得点. // @return ret: 更新した得点のリスト. map<int, int> updateScore(map<int, int> m, int s){ map<int, int> ret; ret[s]++; for(auto &p : m) ret[p.first]++, ret[p.first + s]++; // for(auto &p : ret) cout << "updateScore(ret): " << p.first << " "; // cout << endl; return ret; } int main() { // 1. 入力情報取得. int N; cin >> N; int p[N + 1]; p[0] = 0; for(int i = 1; i < N + 1; ++i) cin >> p[i]; // 2. sort. sort(p, p + N + 1); // 3. ありうる得点を保存. map<int, int> m; m[p[0]]++; for(int i = 1; i < N + 1; i++){ map<int, int> lm = updateScore(m, p[i]); swap(m, lm); } // for(auto &p : m) cout << p.first << " "; // 4. 出力. int ans = 0; for(auto &p : m) if(p.second > 0) ans++; cout << ans << endl; return 0; } |
■参照サイト
Typical DP Contest
No.4 おもりと天秤