Codeforces 480D Parcels(dp)

Codeforces 480D Parcels(dp)

題目鏈接：Codeforces 480D Parcels

題目大意：就是有一個用來堆放貨物的板，承重力為S。現在有N件貨物，每件貨物有到達的時間，運走的時間，以及

重量，承重，存放盈利。如果這件貨物能再運達時間存放，並在指定時間取走的話，就能獲得相應的盈利值。貨物都是

逐個往上疊的，每個箱子上面的總重量不能大於箱子的承重。總的質量不能大於板的承重，貨物上面還有貨物的話是不

能被取走的。現在求最大的盈利值。

解題思路：dp好題，沒想出來，看懂別人代碼A掉的。

首先將貨物按照運走時間早的，運進時間晚的排序，貪心的思想，越早處理掉越早把錢賺了。然後dp[i][j]表示說裝入第i

個貨物，並且當前重量為j的最大收益。

類似與逆思想的方式，從先移動出去的貨物開始考慮，然後向後轉移，因為會有說in3，in1，out1，in2，out2，out3這

樣的情況，即貨物1和貨物2的重量是不需要疊加的，兩個錢都賺的話也不會影響到貨物3，所以f[i]數組用來維護說在i時

刻前已經移走的貨物淨賺最大值。在考慮第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 < b.out || (a.out == b.out && a.in > b.in);
}

int N, S, dp[maxn + 5][maxn * 2 + 5], f[maxn * 2 + 5];

int main () {
    scanf("%d%d", &N, &S);
    p[0] = (Parcel){0, 2 * maxn, 0, S, 0};
    for (int i = 1; i <= N; i++)
        p[i].read();
    sort(p, p + N + 1, cmp);

    for (int i = 0; i <= N; i++) {
        for (int w = p[i].w; w <= S; w++) {
            int o = p[i].in;
            int wi = min(p[i].s, w - p[i].w);
            f[o] = 0;

            for (int j = 0; j < i; j++) if (p[j].in >= p[i].in) {
                while (o < p[j].out) {
                    o++;
                    f[o] = f[o-1];
                }
                f[o] = max(f[o], f[p[j].in] + dp[j][wi]);
            }
            dp[i][w] = f[o] + p[i].v;
        }
    }

    printf("%d\n", dp[N][S]);
    return 0;
}