Codeforces 1203F (贪心， DP)

题意：有n个任务，你的初始rating是m, 这n个任务有两个指标：完成这项任务所需的最低rating(a[i])，以及完成这项任务后rating的变化(可能为负)(b[i])。rating不能为负。F1:问是否存在一种任务完成顺序，始得所有任务都可以被完成,。F2:你可以任意选择一些任务去完成，问最多可以完成多少任务。

思路：

F1: 首先任务分成两部分：涨rating的和降rating的。对于涨rating的任务，直接按照a[i]从小到大排序即可。为什么呢？因为完成rating之后rating一定不会比原来小,即原来能完成的任务在完成其它任务后也一定能完成，如果可以全部完成，就开始考虑降rating的部分。我们考虑一下降rating的部分，我们考虑每一个任务执行之后rating的下界，然后按下界从大到小排序，即优先选择下界大的任务，下界越高对后面的影响越小。

代码：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 110;
struct node {
int x, y;
};
vector<node> a, b;
bool cmp1(node t1, node t2) {
return t1.x < t2.x;
}
bool cmp2(node t1, node t2) {
return (max(t1.x, -t1.y) + t1.y) > (max(t2.x, -t2.y) + t2.y);
}
int main() {
int n, m, cnt1 = 0, cnt2 = 0;
scanf("%d%d", &n, &m);
int sum = 0;
node tmp;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &tmp.x, &tmp.y);
if(tmp.y >= 0) a.push_back(tmp);
else b.push_back(tmp);
}
sort(a.begin(), a.end(), cmp1);
sort(b.begin(), b.end(), cmp2);
int ans = 0;
for (int i = 0; i < a.size(); i++) {
if(m < a[i].x) ans = -1;
m += a[i].y;
}
for (int i = 0; i < b.size(); i++) {
if(m < b[i].x) ans = -1;
m += b[i].y;
}
if(ans == -1) printf("NOn");
else printf("YESn");
}

F2:很明显这是一个背包DP,但是直接DP是O(n * n * m)的，因为每一个任务的选择会影响后面的任务。这样DP会超时。通过F1的结论我们得知，如果我们把降rating的部分按照下界排序，优先选择上界高的任务，这样我们DP转移时只需枚举当前任务选择还是不选择就行了，因为这种决策是最优的，所以不需再考虑之前完成的任务的影响，这样O(n * m)的复杂度便可完成DP过程。

代码：

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int maxn = 600010;
int dp[110][maxn];
bool cmp(pii t1, pii t2) {
return (t1.first + t1.second) > (t2.first + t2.second);
}
vector<pii> a, b;
int main() {
int n, m;
scanf("%d%d", &n, &m);
pii tmp;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &tmp.first, &tmp.second);
if(tmp.second >= 0) a.push_back(tmp);
else b.push_back(tmp);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end(), cmp);
int mx = m, tot = 0;
for (int i = 0; i < a.size(); i++) {
if(a[i].first <= mx) {
mx += a[i].second;
tot++;
}
}
int ans = 0;
dp[0][mx] = tot;
for (int i = 0; i < b.size(); i++) {
for (int j = 0; j <= mx; j++) {
if(j >= b[i].first && j + b[i].second >= 0) {
dp[i + 1][j + b[i].second] = max(dp[i + 1][j + b[i].second], dp[i][j] + 1);
}
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
}
}
for (int i = 0; i <= mx; i++) {
ans = max(ans, dp[b.size()][i]);
}
printf("%dn", ans);
}