P1417 烹调方案 TJ

题目链接

思路

大眼一看是一个背包问题，但是多了一个附属条件 (b_i)，那么我们可以考虑两个物品的先后顺序如何最优。
考虑两个物品 (x ,y)。
如果 (x) 在 (y) 之前选的话，收益就是：
(a_x - b_x imes (t + c_x) + a_y - b_y imes (t + c_x + c_y)~~~~~~~~①)，
如果 (x) 在 (y) 之后选的话，收益就是：
(a_y - b_y imes (t + c_y) + a_x - b_x imes (t + c_y + c_x)~~~~~~~~②)。
如果想让 (x) 先选，那么必须使 (① > ②)，即：
(a_x - b_x imes (t + c_x) + a_y - b_y imes (t + c_x + c_y) > a_y - b_y imes (t + c_y) + a_x - b_x imes (t + c_y + c_x))，
化简得:
(b_y imes c_x < b_x imes c_y)
所以我们关键字排序一下就可按普通 (01) 背包来做了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXT = 1e5 + 10;
const int MAXN = 5e1 + 10;
ll T ,n;
struct node {
	ll a ,b ,c;
}ar[MAXN];
bool cmp (node r1 ,node r2) {
	return r1.c * r2.b < r2.c * r1.b;
}
ll dp[MAXT];
int main () {
	scanf ("%lld%lld",&T ,&n);
	for (int q = 1;q <= n;++ q) {
		scanf ("%lld",&ar[q].a);
	}
	for (int q = 1;q <= n;++ q) {
		scanf ("%lld",&ar[q].b);
	}
	for (int q = 1;q <= n;++ q) {
		scanf ("%lld",&ar[q].c);
	}
	sort (ar + 1 ,ar + n + 1 ,cmp);
	dp[0] = 0;
	for (int q = 1;q <= n;++ q) {
		for (int w = T;w >= ar[q].c;-- w) {
			dp[w] = max (dp[w - ar[q].c] + ar[q].a - ar[q].b * w ,dp[w]);
		}
	}
	ll ans = 0;
	for (int q = 1;q <= T;++ q) {
		ans = max (ans ,dp[q]);
	}
	printf ("%lld
",ans);
	return 0;
}