動的計画法：少し考察を要する問題（5題）
プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
この本（通称「蟻本」）の章末で紹介されている練習問題を淡々と解いている。
今回は動的計画法の第三弾。難しかった。しかも解いてから数日経ったら、どんな問題だったかも忘れてしまったので、とりあえずAcceptされたコードだけ貼り付けておく。適当。
POJ1065: Wooden Sticks
問題概要
(長さl、重さw)が与えられている棒がn本ある。棒をある順番に並べて「セットアップ」する。セットアップにかかる時間は次のルールに従う。
(a) 最初の棒のセットアップは1分
(b) 前の棒が(l,w)で次の棒が(l',w')とする。「l <= l' && w <= w'」が成り立つならば、次の棒のセットアップにかかる時間は0分、成り立たないならば1分である。
うまく棒を並べ替えて最小セットアップ時間を求めよ。
要するに、「l <= l' && w <= w'」が成り立たない場所を最小にせよってことだ。
解法
こんな感じだ↓
POJ (PKU) 1065 : Wooden Sticks - fura_2の日記
#include <iostream> #include <cmath> #include <vector> #include <queue> #include <utility> #include <algorithm> #include <set> using namespace std; int main() { // 入力 int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); vector< pair<int,int> > lw(n); int l, w; for (int i = 0; i < n; i++) { scanf("%d%d", &l, &w); lw[i] = make_pair(l,w); } sort(lw.begin(), lw.end()); // 計算 multiset<int> ter; // 末端の集合 multiset<int>::iterator it; for (int i = 0; i < n; i++) { // w <= new_w なる末端のうち最大のものを探す // new_w < w なる最初のwの一個手前 it = ter.upper_bound(lw[i].second); if (it == ter.begin()) { ter.insert(lw[i].second); } else { ter.erase(--it); ter.insert(lw[i].second); } } // 出力 cout << ter.size() << endl; } }
POJ1631: Bridging signals
問題概要
蟻本P.63そのもの
最長増加部分裂問題(実際には最長減少部分列をも求める)
解法
長さに対する最小の最終要素をdpで計算する。
dp[i] = (長さがi+1であるような部分増加列における最終要素の最小値)
存在しない場合はd[i] = INF
a[j]に対して、a[j] <= dp[i]なる最小のiを探せばいいので、dp内を二分探索
#include <iostream> #include <cmath> #include <vector> #include <queue> #include <utility> #include <algorithm> using namespace std; const int INF = 1000000000; const int N = 40000; int main() { // 入力 int testcase, p, a[N], dp[N], res; scanf("%d", &testcase); while (testcase--) { scanf("%d", &p); for (int i = 0; i < p; i++) { scanf("%d", &a[i]); } // 最長増加部分列 fill(dp, dp + N, INF); for (int i = 0; i < p; i++) { *lower_bound(dp, dp + p, a[i]) = a[i]; } res = lower_bound(dp, dp + p, INF) - dp; cout << res << endl; } }
POJ3666: Making the Grade
問題概要
長さNの数列が与えられる。
各項に数を加えたり減らしたりして、広義単調増加列または広義単調減少列にするための最小コストを求めよ。
解法
POJ-3666 : Making the Grade - komiyamの日記
座標圧縮の発想を使うんだけど、実際に座標圧縮したコードは Time Limit Exceeded をくらった。
#include <iostream> #include <cmath> #include <vector> #include <map> #include <set> #include <queue> #include <utility> #include <algorithm> // #include <cstdlib> using namespace std; const int INF = 1000000000; const int MAX_N = 2000; int N; vector<int> a, sort_a; vector< vector<int> > dp; multiset<int> m_sort_a; // // 座標圧縮 // void compress() { // map<int, int> mp; // // copy(a.begin(), a.end(), sort_a.begin()); // sort(sort_a.begin(), sort_a.end()); // // int val = 0; // for (int i = 0; i < N; i++) { // mp.insert( make_pair(sort_a[i], i) ); // } // // for (int i = 0; i < N; i++) { // a[i] = mp[ a[i] ]; // } // return; // } // 増加列と減少列で２回使う int solve() { int _min; fill(dp[0].begin(), dp[0].end(), 0); int i, j; for (i = 1; i <= N; i++) { _min = INF; for (j = 0; j < N; j++) { _min = min(_min, dp[i-1][j]); dp[i][j] = abs(a[i-1] - sort_a[j]) + _min; } } // 結果 int res = INF; for (int i = 0; i < N; i++) { res = min(res, dp[N][i]); } return res; } int main() { // 入力 cin >> N; a = vector<int>(N); dp = vector< vector<int> >(N+1, vector<int>(N)); int tmp; for (int i = 0; i < N; i++) { scanf("%d", &tmp); a[i] = tmp; m_sort_a.insert(tmp); } // 座標圧縮 // compress(); // 座標圧縮じゃなくてこっちのほうがよかった sort_a = vector<int>(m_sort_a.begin(), m_sort_a.end()); sort(sort_a.begin(), sort_a.end()); // 出力 int res = solve(); reverse(a.begin(), a.end()); res = min(res, solve()); cout << res << endl; }
POJ2392: Space Elevator
2392 -- Space Elevator
個数制限付き部分和問題
ひさしぶりに一発Accepted!!
#include <iostream> #include <cmath> #include <vector> #include <queue> #include <utility> #include <algorithm> using namespace std; const int MAX_A = 40001; struct block { int h, a, c; bool operator<( const block& other ) const { return a < other.a; } }; int main() { // ifstream cin( "test.txt" ); // 入力 int n, _n; vector< block > b; int h, a, c; cin >> n; _n = n; while (_n--) { cin >> h >> a >> c; block bl = {h, a, c}; b.push_back(bl); } sort(b.begin(), b.end()); // dp[i][j] = (i番目までで高さjを作るとa[i]が何個あまるか) int dp[MAX_A]; fill(dp, dp + MAX_A, -1); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < MAX_A; j++) { if (j > b[i].a) { continue; } if (dp[j] >= 0) { dp[j] = b[i].c; } else if (j - b[i].h >= 0 && dp[ j - b[i].h ] > 0) { dp[j] = dp[ j - b[i].h ] - 1; } else { dp[j] = -1; } } } int res = 0; for (int i = 0; i < MAX_A; i++) { res = (dp[i] >= 0) ? i : res; } cout << res << endl; }
POJ2184: Cow Exitbition
問題概要
N頭の牛それぞれに賢さs[i]と面白さf[i]が与えられている。
次の条件を満たす牛の部分集合を求め、TS+TFを出力せよ。
「TS >= 0 かつ TF >= 0 のもとでTS+TFが最大である」
1 <= N <= 100
- 1000 <= s[i] <= 1000
- 1000 <= f[i] <= 1000
解法
dp[i][j] = (i番目までで、TS=jのときのTFの最大値)
#include <iostream> #include <cmath> #include <vector> #include <queue> #include <utility> #include <algorithm> using namespace std; const int INF = 1000000000; const int S_WIDTH = 200001; const int S_HALF = 100000; int main() { // ifstream cin("test.txt"); int n; vector<int> s; vector<int> f; cin >> n; int _s, _f, add_to_res = 0; while(n--) { cin >> _s >> _f; if (_s <= 0 && _f <= 0) { continue; } else if (_s >= 0 && _f >= 0) { add_to_res += _s + _f; } else { s.push_back(_s); f.push_back(_f); } } int m = s.size(); // dp[i][j] = (i番目までで、TS=jのときのTFの最大値) // TS < 0 もありうるので、TS = j - 100000 としよう vector<int> dp(S_WIDTH, -INF); dp[ S_HALF ] = 0; for (int i = 0; i < m; i++) { if (s[i] < 0) { for (int j = 1000; j < S_WIDTH - 1000; j++) { dp[j] = max(dp[j], dp[ j - s[i] ] + f[i]); } } else { for (int j = S_WIDTH - 1000; j >= 1000; j--) { dp[j] = max(dp[j], dp[ j - s[i] ] + f[i]); } } } int res = 0; for (int j = S_HALF; j < S_WIDTH; j++) { if (dp[j] >= 0) res = max(res, j - S_HALF + dp[j]); } res += add_to_res; cout << res << endl; }
