由于你的帮助，火星只遭受了最小的损失。但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
【输出格式：】
输出最大美味指数
[算法分析：]
看似无法用DP做，因为在t时刻完成第i样食材则得到ai-t*bi的美味指数，而不是ai
完成食材的顺序不定，获得的最大美味指数也是不同的。
如果条件是“完成第i样食材获得ai的美味指数”，就是简单的01背包。
那如何使得顺序是最优（即同一时刻做的食材美味指数大的放在前面）呢？
对于两个食材x, y，设t为已用时间
先做x的美味指数为：
a[x] - t * b[x] + a[y] - (t + c[x]) * b[y]
= a[x] - t * b[x] + a[y] - t * b[y] - c[x] * b[y]
= a[x] + a[y] - t * (b[x] + b[y]) - c[x] * b[y]
先做y的美味指数为：
a[y] - t * b[y] + a[x] - (t + c[y]) * b[x]
= a[y] - t * b[y] + a[x] - t * b[x] - c[y] * b[x]
= a[x] + a[y] - t * (b[x] + b[y]) - c[y] * b[x]
不难看出，如果要使得先做x的美味指数>先做y的美味指数，则c[x] * b[y] < c[y] * b[x]，
即这道题的排序规则
剩下的事情就是01背包了
[Code:]
1 //P1417 烹调方案 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 typedef long long LL; 7 8 const int MAXN = 50 + 1; 9 const int MAXM = 100000 + 1; 10 11 int n, T; 12 LL f[MAXM]; 13 struct Food { 14 LL a, b, c; 15 }h[MAXN]; 16 17 inline bool cmp(Food x, Food y) { 18 return y.b * x.c < x.b * y.c; 19 } 20 21 int main() { 22 scanf("%d%d", &T, &n); 23 for(int i=1; i<=n; ++i) scanf("%lld", &h[i].a); 24 for(int i=1; i<=n; ++i) scanf("%lld", &h[i].b); 25 for(int i=1; i<=n; ++i) scanf("%lld", &h[i].c); 26 sort(h + 1, h + n + 1, cmp); 27 for(int i=1; i<=n; ++i) 28 for(int j=T; j>=h[i].c; --j) 29 f[j] = max(f[j], f[j - h[i].c] + h[i].a - j * h[i].b); 30 LL ans = 0; 31 for(int i=1; i<=T; ++i) 32 ans = max(ans, f[i]); 33 printf("%lld ", ans); 34 }