题解 P4937 【Portal1】

· · 题解

MasterOJ

看到题目描述，消耗时间？价值？

不就是一个背包吗？

不过加了一个时间限制，那么本来循环从T_i~MAX_T，就改成T_i~D_i，高高兴兴地写完代码

    for (RI i = 1; i <= N; ++i) {
        scanf("%d%d%d", &T, &D, &C);
        if (D > mx)
            mx = D;
        for (RI j = D - 1; j >= T; --j) {
            if (f[j - T] + C > f[j]) {
                g[j] = g[j - T];
                g[j].push_back(i);
                f[j] = f[j - T] + C;
            }
        }
    }

太高兴了，T,D,C连数组都不用开了

再循环扫一遍f就行了

    int ans = -1;
    int mni = -1;
    for (RI i = 1; i <= mx; ++i)
        if (f[i] > ans)
            ans = f[i], mni = i;
    printf("%d\n", ans);
    printf("%d\n", g[mni].size());
    for (vector<int>::iterator it = g[mni].begin(); it < g[mni].end(); it++)
        printf("%d ", *it);

emmm，全是WA，只有25分

问题出在哪里呢？

普通的背包的限制都是Max_T，所有人的限制都是一样的，肯定不会越界。但是这次的限制不一样，你只是保证了当前没有超时，而不能保证前面的没有超时。

一个修正就出来了：对D_i从小到大排序扫。

为什么这样可以保证不会超时呢？

证明：D_i从小到大排序，时间限制保证了前面的比后面的低，这样后面的操作肯定会比前面的宽裕，这样就不会影响到了。。。

贴个代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define RI register int

using namespace std;

struct Node {
    int T, D, C, id;
    bool operator < (const Node& b) {
        return this->D < b.D;
    }
}a[105];

int main() {
    int N;
    scanf("%d", &N);
    int mx = -1;
    int f[2005];
    vector<int> g[2005];
    memset(f, 0, sizeof(f));
    for (RI i = 1; i <= N; ++i) {
        scanf("%d%d%d", &a[i].T, &a[i].D, &a[i].C);
        a[i].id = i;
        if (a[i].D > mx)
            mx = a[i].D;
    }
    sort(a + 1, a + N + 1);
    for (RI i = 1; i <= N; ++i) {
        for (RI j = a[i].D - 1; j >= a[i].T; --j) {
            if (f[j - a[i].T] + a[i].C > f[j]) {
                g[j] = g[j - a[i].T];
                g[j].push_back(a[i].id);
                f[j] = f[j - a[i].T] + a[i].C;
            }
        }
    }
    int ans = -1;
    int mni = -1;
    for (RI i = 1; i <= mx; ++i)
        if (f[i] > ans)
            ans = f[i], mni = i;
    printf("%d\n", ans);
    printf("%d\n", g[mni].size());
    for (vector<int>::iterator it = g[mni].begin(); it < g[mni].end(); it++)
        printf("%d ", *it);
    return 0;
}