Luogu P1899 魔法物品
题目描述：
有两种类型的物品：普通物品和魔法物品。普通物品没有魔法属性，而魔法物品拥有一些魔法属性。每种普通物品有一个价值(P)，但每种魔法物品有两种价值：鉴定前的价值(P_{1})和鉴定后的价值(P_{2})（当然，(P_{1})总是大于(P_{2})）。
为了鉴定一个魔法物品，你需要购买一个魔法卷轴，用它来鉴定魔法物品。鉴定完一件魔法物品之后，鉴定卷轴就会消失。每个鉴定卷轴需要(S)元钱，如果没有足够的钱，你将无法购买任何魔法卷轴。
现在，你正在一个集市中，同时拥有很多物品。你知道每件物品的价值并且想要出售全部物品。那么，你最多可以获得多少钱呢？
你可以假定：
- 开始的时候你没有钱。
- 所有的魔法物品还没有被鉴定。
- 只要你有足够的钱，你可以购买任意多的魔法卷轴。
输入输出格式：
输入格式（magic.in）：
第一行有两个整数(N)和(S)((0 < S leqslant 10000))，表示你拥有的物品数和一个鉴定卷轴价格。
接下来(N)行，每行给出一件物品的价格。
对于每件普通物品，那一行仅有一个整数(P)((0 < P leqslant 10000))。
对于每件普通物品，那一行将会有两个整数(P_{1})和(P_{2})((0 < P_{1} < P_{2} leqslant 10000))。
输出格式（magic.out）：
一个整数表示你最多能够获得多少钱。
样例：
输入#1:
2 10 10 20 100输出#1:
100数据规模：
对于30%的数据，(N leqslant 50)；
对于100%的数据，(N leqslant 1000)。
题解：
首先考虑输入时的处理。显然在处理普通物品的时候，可以直接选择把他们卖掉，作为买卷轴的本钱。其次考虑魔法物品。当魔法物品的(P_{2})减掉(S)不大于(P_{1})时，把它卖掉也是一定一的可以的。由此，我们将只把(P_{2} - S geqslant P_{1})的魔法物品存下来。
其次进行对魔法物品的处理。(为方便表示，设(ans)为卖掉所有可卖物品后手中的金钱，(P_{i,1}, P_{i, 2})分别代表第(i)个待处理魔法物品的(P_{1}, P_{2})，(tot)为所有物品的(P_{1}))。
- 首先是当(ans geqslant S)时。因为所有待处理的物品(i)都满足(P_{i, 2} - S geqslant P_{i, 1})，所以，先买到一个魔法卷轴、鉴定并且出售第一个魔法物品后，(ans)的值一定比买卷轴之前大。所以直接把所有未处理的魔法物品进行鉴定，然后按魔法价格售出即可。
- 其次是当(ans < S)时。我们需要售出一些魔法物品使(ans geqslant S)，之后即可按上一种情况处理。这个时候就需要跑个DP来计算卖哪个（哪些）比较优。可得(P_{i, 2} - S - P_{i, 1})为第(i)个物品的损失，转移方程：(F[j] = min(F[j], f[j - P_{i, 1}] + (P_{i, 2} - S - P_{i, 1})))(其中(F[j])为不算(ans)在内，再得到(j)元时所产生的最小损失和)。跑一遍DP计算最小的损失（设为(minn)）((S - ans leqslant j leqslant tot))。如果能够凑出使(ans geqslant S)的金钱的话，则按情况一处理，然后(ans - minn)即可；如果不能，意味着一个魔法卷轴都买不到，直接输出(tot)即可。
另：如果单纯按情况二写的话，时间复杂度会出锅（(N * tot leqslant 1e^{10})）；所以需要将DP稍微优化一下：令(F[j])代表当所得金钱(geqslant j) 时最小的代价和。转移方程：(F[j] = min(f[j], f[max(j - P_{i, 1}, 0)] +(P_{i, 2} - S - P_{i, 1})))。（(N * S leqslant 5e^{6})）
代码：
#include <cstdio>
const int INF = 999999999;
const int MAXP = 5000;
int n, s, top, ans, tmp, tmp2, tmp3, tot, xxx;
int p[1010], o[1010], f[5001];
char c(0);
inline int min(int a, int b) {
return (a < b ? a : b);
}
inline int max(int a, int b) {
return (a > b ? a : b);
}
int main() {
scanf("%d%d", &n, &s);
for (int i = 1; i <= n; ++i) {
scanf("%d", &tmp);
tot = tot + tmp;
scanf("%c", &c);
if(c == ' ') {
scanf("%d", &tmp2);
if(tmp2 - s > tmp) {
p[++top] = tmp2;
o[top] = tmp;
}
else ans = ans + tmp;
} else {ans = ans + tmp;}
}
xxx = ans; //存储ans的值，因为下一步要对ans进行操作
for (int i = 1; i <= top; ++i) //按情况一处理
ans = ans + p[i] - s;
if(xxx < s){ //如果为情况二
tmp3 = min(MAXP, tot); //因为f[j]代表了大于等于j的最小值，所以DP跑到卷轴价格的最大值5000即可
for (int i = 1; i <= tmp3; ++i) f[i] = INF;
for (int i = 1; i <= top; ++i) {
tmp = o[i]; tmp2 = p[i] - s - tmp;
for (int j = tmp3; j >= 1; j--)
f[j] = min(f[j], f[max(j - tmp, 0)] + tmp2); //取max(j-tmp,0)以免得负值
}
int minn(INF);
for (int i = s - xxx; i <= tmp3; ++i) //取最小代价和
minn = min(minn, f[i]);
if(minn < INF) printf("%d
", ans - minn); //
else printf("%d
", tot);
} else {printf("%d
", ans); return 0;}
return 0;
}