10154 Weights and Measures

題目連結

題目翻譯

Yertle 國王要用烏龜疊成一座王座，每隻烏龜都有各自的體重與承重力（承重力包含自己的體重在內，例如一隻體重 300g、承重力 1000g 的烏龜，背上最多能承受 700g 的烏龜）。請幫忙決定疊放順序，使疊起來的烏龜塔盡可能高。

輸入

標準輸入包含多行，每行是兩個以空白分隔的整數，分別代表一隻烏龜的體重與承重力（單位皆為公克），最多有 5,607 隻烏龜。

輸出

輸出一個整數，代表在不超過任何一隻烏龜承重力的前提下，最多能疊起的烏龜數量。

解題思路

這是經典的「最長鏈型」DP 問題：把烏龜依承重力由小到大排序（承重力小的要盡量放在塔的上層），用 dp[j] 表示「疊 j 隻烏龜（由上層往下疊）時，目前最上面這 j 隻烏龜的總重量最少是多少」，初始 dp[0] = 0、其餘為極大值。依承重力由小到大依序處理每隻烏龜 i（體重 w、承重力 s），從大到小更新 j：若 dp[j-1] + w ≤ s（代表這隻烏龜扛得住上面疊的 j-1 隻）且比目前的 dp[j] 更小，就用 dp[j-1] + w 更新 dp[j]，並用 mx 記錄曾經成功更新過的最大 j。掃描完所有烏龜後，mx 就是答案。

程式碼

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

#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>

signed main() { WA();
    vector<PII> v;
    for (int a, b; cin >> a >> b;) v.pb({b, a});
    sort(all(v));
    vector<int> dp(v.size()+1, INF); dp[0] = 0;
    int mx = 0;
    for (int i = 0; i < v.size(); i++) {
        for (int j = v.size(); j > 0; j--) {
            if (dp[j-1]+v[i].se <= v[i].fi && dp[j-1]+v[i].se < dp[j]) {
                dp[j] = dp[j-1]+v[i].se;
                mx = max(mx, j);
            }
        }
    }
    cout << mx << '\n';
}