ZeroJudge 解題筆記：f455. 詠竣的哀鳳12

作者：王一哲
日期：2025年10月12日


ZeroJudge 題目連結：f455. 詠竣的哀鳳12

解題想法

這題是背包問題，用動態規畫處理，但是用 Python 好像沒辦法通過。

Python 程式碼

只能通過 60% 的測資。

t, n = map(int, input().split())  # 總時數 t，工作數量 n
dp = [0]*(t+1)  # 總時數 0 ~ t 對應的最大收入
work = ""  # 最高時薪的工作名稱
imax = 0.0  # 最高時薪
for _ in range(n):  # 執行 n 次
    s, m, h = input().split()  # 工作名稱，收入，需要的時間
    m = int(m); h = int(h)  # m, h 轉為 int
    mph = 1.0*m/h  # 時薪
    if mph > imax:  # 如果時薪較高，更新 imax, work
        imax = mph; work = s
    if h > t: continue  # 如時需要的時間大於 t，不能接工作，找下一筆
    for i in range(t, h-1, -1):  # 倒著更新 dp[t] ~ dp[h]
        dp[i] = max(dp[i], dp[i-h] + m)  # 如果接這個工作總收入變高則更新 dp[i]
print(dp[-1])  # 最高總收入在 dp[t-1], dp[-1]
print(work)  # 印出最高時薪的工作名稱

C++ 程式碼

使用時間約為 0.3 s，記憶體約為 704 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t, n; cin >> t >> n;  // 總時數 t，工作數量 n
    int dp[t+1] = {0};  // 總時數 0 ~ t 對應的最大收入
    string work;  // 最高時薪的工作名稱
    float imax = 0.0;  // 最高時薪
    for(int i=0; i<n; i++) {  // 執行 n 次
        string s; int m, h;  // 工作名稱，收入，需要的時間
        cin >> s >> m >> h;
        float mph = 1.0*m/h;  // 時薪
        if (mph > imax) {  // 如果時薪較高，更新 imax, work
            imax = mph; work = s;
        }
        if (h > t) continue;  // 如時需要的時間大於 t，不能接工作，找下一筆
        for(int j=t; j>=h; j--) {  // 倒著更新 dp[t] ~ dp[h]
            if (dp[j-h] + m > dp[j]) {  // 如果接這個工作總收入變高則更新 dp[j]
                dp[j] = dp[j-h] + m;
            }
        }
    }
    cout << dp[t-1] << "\n" << work << "\n";  // 印出答案
    return 0;
}