题解 CF1203F2 【Complete the Projects (hard version)】

### 思路 **选择既有个数的限制，又有选择顺序的限制** **是不是很像背包问题加贪心的结合版** 我们可以先用贪心决定选择的顺序，最后使用背包完成数量的选择 - 贪心 - 对于$b[i] > 0$按$a[i]$排序 - 对于$b[i] < 0$按$a[i] + b[i]$排序 - [证明链接](https://www.luogu.org/blog/qcwlmqy/solution-cf1203f1) - DP - 状态$dp[i]$表示rating为$i$时，最多完成项目数 - 状态转移方程`$dp[i + b[i]] = max(dp[i] + 1, dp[i + b[i])$ ### 代码 DP ```cpp for (int i = 1; i <= ml; i++) { for (int j = 60000; j >= a[i].first; j--) if (dp[j] != -1) dp[j + a[i].second] = max(dp[j] + 1, dp[j + a[i].second]); } for (int i = 1; i <= mr; i++) { for (int j = b[i].first; j <= 60000; j++) if (dp[j] != -1 && j + b[i].second >= 0) dp[j + b[i].second] = max(dp[j] + 1, dp[j + b[i].second]); } ``` AC ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef pair<int, int> pii; const int maxn = 105; pii a[maxn], b[maxn]; bool cmp_a(const pii& a, const pii& b) { if (a.first == b.first) return a.second > b.second; return a.first < b.first; } bool cmp_b(const pii& a, const pii& b) { if (a.first + a.second == b.first + b.second) return a.second > b.second; return a.first + a.second > b.first + b.second; } int dp[66666]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, r, x, y; cin >> n >> r; int ml = 0, mr = 0; for (int i = 1; i <= n; i++) { cin >> x >> y; if (y >= 0)a[++ml] = pii(x, y); else b[++mr] = pii(x, y); } int k = ml; sort(a + 1, a + 1 + ml, cmp_a); sort(b + 1, b + 1 + mr, cmp_b); memset(dp, -1, sizeof(dp)); dp[r] = 0; for (int i = 1; i <= ml; i++) { for (int j = 60000; j >= a[i].first; j--) if (dp[j] != -1) dp[j + a[i].second] = max(dp[j] + 1, dp[j + a[i].second]); } for (int i = 1; i <= mr; i++) { for (int j = b[i].first; j <= 60000; j++) if (dp[j] != -1 && j + b[i].second >= 0) dp[j + b[i].second] = max(dp[j] + 1, dp[j + b[i].second]); } int ans = -1; for (int i = 0; i <= 60000; i++)ans = max(dp[i], ans); cout << ans << '\n'; } ```