<html>-白红宇

<html>

阅读量：6281 次

发布时间：2019-06-22

本文共 2184 字，大约阅读时间需要 7 分钟。

题目大意：就是有一个用来堆放货物的板。承重力为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;}

标签：

本文已收录于下面专栏：

0条评论

在线课程

你可能感兴趣的文章

0条评论

相关文章推荐

在线课程