难度：普及+/提高

题目背景

        由于你的帮助，火星只遭受了最小的损失。但gw懒得重建家园了，就造了一艘飞船飞向遥远的earth星。不过飞船飞到一半，gw发现了一个很严重的问题:肚子饿了~
        gw还是会做饭的，于是拿出了储藏的食物准备填饱肚子。gw希望能在T时间内做出最美味的食物，但是这些食物美味程度的计算方式比较奇葩，于是绝望的gw只好求助于你了。

题目描述

        一共有n件食材，每件食材有三个属性，ai，bi和ci，如果在t时刻完成第i样食材则得到ai-t*bi的美味指数，用第i件食材做饭要花去ci的时间。
        众所周知，gw的厨艺不怎么样，所以他需要你设计烹调方案使得美味指数最大

输入输出格式

输入格式:

        第一行是两个正整数T和n，表示到达地球所需时间和食材个数。
        下面一行n个整数，ai
        下面一行n个整数，bi
        下面一行n个整数，ci

输出格式:

        输出最大美味指数

数据范围
        对于40%的数据1≤n≤10
        对于100%的数据1≤n≤50
        所有数字均小于100，000

输入输出样例

Sample input

74 1
502
2
47

Sample output

408

题解

        题目考察线性动态规划，也属于基本的01背包问题，但本题相比背包问题更能体现出问题的本质。
        在经典的01背包问题即第二题采药中，物品的顺序是不影响最终结果的。这个结论显然，因为物品无论先加入还是后加入，它们占据背包的空间不变，价值也不变，对其它物品也不会造成实质上的影响。
        但本题不同，本题中物品的价值随着时间的增长而减小，所以对于两个物品，将哪一个放到前面会直接影响结果。也就是说只有把B放于A前或反之时才有最优解。我们在DP时必须遵从这个会出现最优解的顺序来加入物品，即要先对物品进行排序。
        但是，排序的标准是什么?
        考虑两个物品，假定在时刻p开始加入背包，则将第一个物品先放入随机放入第二个时的价值为:

        反之时总价值为:

        令$v_1<v_2$，进行运算，得到:

        这个不等式是本题的关键，它说明:只要有上述不等式成立，第二个物品较第一个物品先放入背包会有最优解。
        为了最大程度利用时间，没有哪一时刻是空闲的，也就是说当一个物品放置结束时(即烹饪完一个食材)立即开始下一个物品的放入。倘若任何两个相邻放置的物品都符合上述的不等式，容易知这时的物品放入顺序会出现最优解。下面是简单证明:
        倘若物品顺序不符合这个排序规则时有最优解，一定会出现两个相邻的物品违反上述不等式的情况，这时由上面的推导过程知将两个物品放入顺序调换后会得到更多的价值总和，这与最优解矛盾。故仅有按上述排序规则排出的放入顺序才会有最优解。
        按照这个原则排序后再按照01背包问题的DP思路进行即可。注意这里的状态转移方程与01背包不完全相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<algorithm>

using namespace std;
long long t, n;

struct node {
    long long a, b, c;

    bool operator<(node p) {
        return c * p.b < b * p.c;
    }
} op[51];

long long vis[60][100001] = {0};

int main() {
    cin >> t >> n;
    for (int i = 1; i <= n; i++)cin >> op[i].a;
    for (int i = 1; i <= n; i++)cin >> op[i].b;
    for (int i = 1; i <= n; i++)cin >> op[i].c;
    sort(op + 1, op + n + 1);
    for (register int i = n; i >= 1; i--) {
        for (register long long j = t; j >= 1; j--) {
            if (op[i].c + j - 1 > t)vis[i][j] = vis[i + 1][j];
            else vis[i][j] = max(op[i].a - (j + op[i].c - 1) * op[i].b + vis[i + 1][j + op[i].c], vis[i + 1][j]);
        }
    }
    cout << vis[1][1];
    return 0;
}