這道CSP41-B《機器人項目管理》的核心其實非常清晰普通型任務(wù) 0/1 背包靈活型任務(wù) 可以任意切分咖啡因此按“單位咖啡收益”貪心。但真正的難點在于這兩種任務(wù)混在一起時怎么組合一、先把題目翻譯成數(shù)學問題有n個任務(wù)。第i個任務(wù)o[i]任務(wù)類型 t[i]原始耗時 a[i]最多能喝多少杯咖啡 b[i]喝滿 a[i] 杯后最多縮短多少時間初始總時間T∑ti我們有最多m杯咖啡。目標是讓總時間盡可能小。等價于讓總減少時間盡可能大。所以問題可以轉(zhuǎn)化為m 杯咖啡 ↓ 如何分配 ↓ 獲得最大的“時間減少量”最后答案∑ti?最大減少時間答案\sum t_i-最大減少時間題目中靈活型和普通型的規(guī)則分別如下。二、靈活型任務(wù)是什么假設(shè)a 5 b 10喝滿5 杯咖啡減少10 時間那么靈活型可以喝任意實數(shù)杯。例如咖啡減少時間00122.5548510因為它是線性的。如果給x杯咖啡減少時間bi / ai *x所以每杯咖啡的收益是bi / ai這個值非常重要。三、靈活型任務(wù)應(yīng)該怎么分配假設(shè)有三個任務(wù)任務(wù) 1a 2b 10任務(wù) 2a 4b 12任務(wù) 3a 5b 10每杯咖啡收益任務(wù) 110 / 2 5任務(wù) 212 / 4 3任務(wù) 310 / 5 2那么應(yīng)該先給任務(wù) 1 再給任務(wù) 2 最后給任務(wù) 3也就是說靈活型任務(wù)按照 bi / ai從大到小貪心。四、普通型任務(wù)有什么不同普通型任務(wù)只能不喝 或者一次喝滿 a[i] 杯例如a 5 b 10只能選擇0 杯 → 減少 0或者5 杯 → 減少 10不能3 杯 → 減少 6所以普通型任務(wù)就是重量 a[i] 價值 b[i] 的一個物品。這就是標準的0/1 背包設(shè)dp[j]表示 使用j杯咖啡普通型任務(wù)最多能減少多少時間。轉(zhuǎn)移for (int j m; j a[i]; j--) { dp[j] max(dp[j], dp[j - a[i]] b[i]); }注意一定要從大到小因為每個普通型任務(wù)只能選一次。五、混合情況才是真正的核心假設(shè)我們先決定普通型任務(wù)用了 j 杯咖啡那么剩余咖啡 m - j剩下的全部給靈活型任務(wù)。因此總減少時間 普通型任務(wù)減少時間 靈活型任務(wù)減少時間也就是dp[j]flex(m?j)其中dp[j]表示用普通型任務(wù)消耗j杯咖啡最大減少時間。而flex(x)表示用x杯咖啡給靈活型任務(wù)最大能減少多少時間。最后枚舉for (int j 0; j m; j) { ans max(ans, dp[j] flex(m - j)); }六、靈活型的flex(x)怎么計算假設(shè)靈活任務(wù)是任務(wù)ab單位收益A2105B393C482排序后A → B → C也就是每杯減少時間 5 3 2假設(shè)x 4 杯咖啡先給 AA 最多需要 2 杯 減少 10還剩2 杯給 B每杯減少 3所以總共10 6 16因此flex(4)16七、如何高效計算所有flex(x)因為m 1000 n 200其實直接計算都不會太慢。但我們可以先排序struct Task { int a, b; }; sort(flex.begin(), flex.end(), [](Task x, Task y) { return 1.0 * x.b / x.a 1.0 * y.b / y.a; });不過這里有精度問題。更好的比較方式是b1/a1b2/a2等價于b1*a2b2*a1所以sort(flex.begin(), flex.end(), [](Task x, Task y) { return 1LL * x.b * y.a 1LL * y.b * x.a; });然后計算double calc(int coffee) { double res 0; for (auto [a, b] : flex) { int use min(coffee, a); res 1.0 * use * b / a; coffee - use; if (coffee 0) break; } return res; }這里為什么use是整數(shù)也沒關(guān)系因為我們最終計算的是普通任務(wù)用了 j 杯其中j是整數(shù)。剩下m - j也是整數(shù)。雖然靈活型允許實數(shù)杯咖啡但對于固定的總咖啡量x把前面的任務(wù)喝滿 最后一個任務(wù)喝 x - 前面使用量這里前面使用的都是整數(shù)a[i]所以剩下仍然是整數(shù)。因此我們只需要計算flex(0) flex(1) ... flex(m)八、完整算法現(xiàn)在整個算法就出來了。第一步計算原始總時間double total 0; for (...) { total t[i]; }第二步普通任務(wù)做 0/1 背包vectordouble dp(m 1, 0);對于每個普通任務(wù)for (int j m; j a; j--) { dp[j] max(dp[j], dp[j - a] b); }第三步靈活任務(wù)排序按照bi / ai從大到小排序。第四步計算flex[x]for (int x 0; x m; x) { int coffee x; for (auto task : flex) { int use min(coffee, task.a); f[x] 1.0 * use * task.b / task.a; coffee - use; if (coffee 0) break; } }第五步枚舉普通任務(wù)使用多少咖啡double best 0; for (int j 0; j m; j) { best max(best, dp[j] f[m - j]); }最終cout fixed setprecision(10) total - best;題目的范圍是n ≤ 200, m ≤ 1000最終代碼如下#include bits/stdc.h using namespace std; using ll long long; struct Task { int a, b; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; double totalTime 0; vectorTask flexible; // dp[j] // 使用普通型任務(wù)恰好/至多消耗 j 杯咖啡時 // 能獲得的最大時間減少量 vectordouble dp(m 1, 0); for (int i 0; i n; i) { int o, t, a, b; cin o t a b; totalTime t; if (o 0) { // 靈活型 flexible.push_back({a, b}); } else { // 普通型0/1 背包 for (int j m; j a; j--) { dp[j] max(dp[j], dp[j - a] b); } } } // 按單位咖啡收益 b / a 從大到小排序 sort(flexible.begin(), flexible.end(), [](const Task x, const Task y) { return 1LL * x.b * y.a 1LL * y.b * x.a; }); // flex[i]i 杯咖啡全部給靈活型任務(wù) // 最多減少多少時間 vectordouble flex(m 1, 0); for (int coffee 0; coffee m; coffee) { int remain coffee; double reduce 0; for (auto task : flexible) { int use min(remain, task.a); reduce 1.0 * use * task.b / task.a; remain - use; if (remain 0) break; } flex[coffee] reduce; } // 枚舉 // j 杯給普通型任務(wù) // m-j 杯給靈活型任務(wù) double bestReduce 0; for (int j 0; j m; j) { bestReduce max(bestReduce, dp[j] flex[m - j]); } double answer totalTime - bestReduce; cout fixed setprecision(10) answer \n; return 0; }