[luogu P1417]烹调方案（贪心，排序，背包）

发表于 分类于 ， ， ， ，
luogu P1417

题目

题目背景

由于你的帮助，火星只遭受了最小的损失。但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

输出格式：
输出最大美味指数

输入输出样例

输入样例#1： 

1
2
3
4
74 1
502
2
47

输出样例#1： 

1
408

说明

【数据范围】

对于40%的数据1<=n<=10

对于100%的数据1<=n<=50

所有数字均小于100,000

【题目来源】

tinylic改编

解题思路

看起来很像一个0-1背包，但是……每个物品的价值在变。
注意到价值的变化与物品的顺序有关，考虑两个相邻物品 $x$ 和 $y$，如果 $x$ 在前 $y$ 在后，那么他俩价值就是
$$a[x]-(p+c[x])*b[x]+a[y]-(p+c[x]+c[y])*b[y]$$
同理，如果 $y$ 在前 $x$ 在后，那么价值是
$$a[y]-(p+c[y])*b[y]+a[x]-(p+c[x]+c[y])*b[x]$$
二者比较大小，化简后得到 $x$ 在前 $y$ 在后更优的充要条件是
$$b[x]*c[y] > b[y]*c[x]$$
所以我们就按它对物品先进行排序，接着挨个考虑是否使用某物品，也就是0-1背包了。

坑：注意开 long long

Code

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
32
# include<cstdio>
# include<algorithm>

using namespace std;

typedef long long LL;

int T, n;
LL dp[100005], ans;

struct Food{
	int a, b, c;
}f[55];
bool cmp(Food x, Food y){
	return 1ll * x.b * y.c > 1ll * y.b * x.c;
}

int main(){
	scanf("%d%d", &T, &n);
	for(int i = 1; i <= n; i++)	scanf("%d", &f[i].a);
	for(int i = 1; i <= n; i++)	scanf("%d", &f[i].b);
	for(int i = 1; i <= n; i++)	scanf("%d", &f[i].c);
	sort(f+1, f+n+1, cmp);
	for(int i = 1; i <= n; i++)
		for(int j = T; j >= 0; j--)
			if(j >= f[i].c)
				dp[j] = max(dp[j], dp[j-f[i].c]+1ll*(f[i].a-1ll*j*f[i].b));
	for(int i = 1; i <= T; i++)
		ans = max(ans, dp[i]);
	printf("%lld\n", ans);
	return 0;
}