Codeforces480DParcels(dp)

题目链接：Codeforces 480D Parcels

题目大意：就是有一个用来堆放货物的板，承重力为S。现在有N件货物，每件货物有到达的时间，运走的时间，以及

重量，承重，存放盈利。如果这件货物能再运达时间存放，并在指定时间取走的话，就能获得相应的盈利&＃20540;。货物都是

逐个往上叠的，每个箱子上面的总重量不能大于箱子的承重。总的质量不能大于板的承重，货物上面还有货物的话是不

能被取走的。现在求最大的盈利&＃20540;。

解题思路：dp好题，没想出来，看懂别人代码A掉的。

首先将货物按照运走时间早的，运进时间晚的排序，贪心的思想，越早处理掉越早把钱赚了。然后dp[i][j]表示说装入第i

个货物，并且当前重量为j的最大收益。

类&＃20284;与逆思想的方式，从先移动出去的货物开始考虑，然后向后转移，因为会有说in3，in1，out1，in2，out2，out3这

样的情况，即货物1和货物2的重量是不需要叠加的，两个钱都赚的话也不会影响到货物3，所以f[i]数组用来维护说在i时

刻前已经移走的货物净赚最大&＃20540;。在考虑第i个货物的时候，需要判断前面i-1个货物，只有在in_i ≤ in_j && out_j ≤ out_i

的时候，才能转移，转移的过程中一并维护f数组。

#include
#include
#include
using namespace std;
const int maxn = 500;
struct Parcel {
int in, out, w, s, v;
void read() {
scanf("%d%d%d%d%d", &in, &out, &w, &s, &v);
}
}p[maxn];
inline bool cmp (const Parcel& a, const Parcel& b) {
return a.out out || (a.out == b.out && a.in > b.in);
}
int N, S, dp[maxn &＃43; 5][maxn * 2 &＃43; 5], f[maxn * 2 &＃43; 5];
int main () {
scanf("%d%d", &N, &S);
p[0] = (Parcel){0, 2 * maxn, 0, S, 0};
for (int i = 1; i <= N; i&＃43;&＃43;)
p[i].read();
sort(p, p &＃43; N &＃43; 1, cmp);
for (int i = 0; i <= N; i&＃43;&＃43;) {
for (int w = p[i].w; w <= S; w&＃43;&＃43;) {
int o = p[i].in;
int wi = min(p[i].s, w - p[i].w);
f[o] = 0;
for (int j = 0; j if (p[j].in >= p[i].in) {
while (o out) {
o&＃43;&＃43;;
f[o] = f[o-1];
}
f[o] = max(f[o], f[p[j].in] &＃43; dp[j][wi]);
}
dp[i][w] = f[o] &＃43; p[i].v;
}
}
printf("%d\n", dp[N][S]);
return 0;
}