2019-1-27-食物

Posted on |

Problem

$n$种物品，每种物品有三个参数$t,u,v$分别代表：贡献，大小，数量。

$m$种背包，每种背包有三个参数$x,y,z$分别代表：容量，花费，数量。

要求贡献和大于等于p时的最小花费。

若花费超过50000或贡献无法不小于p则输出TAT。

PS：对于一份物品来说，它可以被拆开，分成几份运输，但是只有该份物品被运输完全才可以获得贡献。

$n,m<200;p<50000;t,u,v,x,y,z<100$

Solution

多重背包。

将背包的数量拆分成$\sum\limits_{2^i\leq num} 2^i$和剩余部分。

然后跑01背包就可以了。

好了，现在考虑这道题。

看起来我们只要做两次背包即可。

一次对物品，求出贡献大于等于p时所需的最小空间siz。

一次对车，求出空间大于等于siz时所需的最小花费。

但是，这两种背包的处理方式却不同。

对物品，我们设f[i]表示贡献为i时的最小空间。

对车，我们设f[i]表示花费为i时的最大空间。

为什么呢？

因为物品的空间和与车的空间和可能有$2*10^6$，转移直接时间爆炸。

所以，我们将物品空间与车的空间和放在转移的权值内，下标为较小的物品贡献与车的花费。

这样就可以巧妙解决啦~(≧▽≦)/~

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

inline int read(){
	int res = 0, fl = 1;
	char r = getchar();
	for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
	for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
	return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 300;
struct node{
	int val,siz,num;
}fd[Maxn],cr[Maxn];
int f[50010];
int Pow[Maxn];
inline void F01pack(int v,int c,int lim){
	for (int i = lim; i >= 0; --i)
		chkmin(f[min(i + v,lim)],f[i] + c);
}
inline void C01pack(int v,int c,int lim){
	for (int i = lim; i >= c; --i){
		chkmax(f[i],f[i - c] + v);
	}
}
inline void work(int v, int s, int cnt, int lim, bool fl){
	for (int i = 0; i <= 8; ++i)
		if(cnt >= Pow[i]){ 
			if(fl) F01pack(v * Pow[i], s * Pow[i], lim);
			else C01pack(v * Pow[i], s * Pow[i], lim);
			cnt -= Pow[i];
		}
	if(cnt) 
		if(fl) F01pack(v * cnt, s * cnt, lim);
		else C01pack(v * cnt, s * cnt, lim);
}
inline void solve(){
	int n = read(), m = read(), p = read();
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	for (int i = 1; i <= n; ++i)
		fd[i].val = read(), fd[i].siz = read(), fd[i].num = read();
	for (int i = 1; i <= n; ++i) work(fd[i].val, fd[i].siz, fd[i].num, p, 1);
	for (int i = 1; i <= m; ++i)
		cr[i].val = read(), cr[i].siz = read(), cr[i].num = read();
	if(f[p] > 1e9) {printf("TAT\n");return;}
	int lim = f[p];
	memset(f, 0, sizeof f);
	for (int i = 1; i <= m; ++i) work(cr[i].val, cr[i].siz, cr[i].num, 50000, 0);
	if(f[50000] < lim) {printf("TAT\n");return;}
	for (int i = 0; i <= 50000; ++i){
		if(f[i] >= lim){ 
			printf("%d\n",i);
			return;
		}
	}
	printf("TAT\n");
}
int main()
{
	freopen("B.in", "r", stdin);
	freopen("B.out", "w", stdout);
	int t = read();
	Pow[0] = 1;
	for (int i = 1; i <= 10; ++i )Pow[i] = Pow[i - 1] << 1;
	while(t--) {
		solve();
	}
	return 0;
}