食物

评测

2019.01.27

2.食物
问题描述:

辉夜本来是生活在月宫的月之公主。

辉夜从月都弄了很多吃的回到了幻想乡,有$n$中不同的食物,第$i$中食物的美味度为$t_i$,一份食物的大小为$u_i$,共有$v_i$份。但是麻烦的事情出现了,她有把这些食物运回永和亭,于是辉夜便弄来了$m$种运载工具。第$i$种运载工具可以运输大小总和不超过$x_i$的食物,运输一次的费用是$y_i$,总共可以运输$z_i$次。
辉夜打算选取一些食物运回永和亭,他们的美味度之和(每份食物的和,即使他们都是同一种食物)至少是$p$。值得注意的是,一份食物可以被拆成几份分批次运输,达到永和亭后在组装起来。但是如果不把一份食物完整的运过去,是无法得到美味度的。辉夜想知道最少需要花费的运输费用是多少。由于辉夜的预算仅有$50000$,因此如果费用超过这个数或者无法获得$p$的的美味度,输出”TAT”。
$1\leq n,m \le200,0\leq p \le 50000,1\leq t_i,u_i,v_i,x_i,y_i,z_i\le100$

输入格式

第一行一个数$test$,表示有$test$组数据。
对于每组数据,第一行有三个数$n,m,p$。

接下来$n$行,每行三个整数$t,u,v$,描述一种食物。

最后m行,每行三个整数$x,y,z$,描述一种运载工具。

输出格式

对于每组数据,输出辉夜想知道的答案。注意存在误解的情况。

样例输入

4

1 1 7

14 2 1

1 2 2

1 1 10

10 10 1

5 7 2

5 3 34

1 4 1

9 4 2

5 3 3

1 3 3

5 3 2

3 4 5

6 7 5

5 3 8

1 1 1

1 2 1

1 1 1

样例输出

4

14

12

TAT

数据规模与约定

test不会太大。

对于前20%的数据,$n,m\leq20$。

对于前50%的数据,$n,m\leq30,t_i,u_i,v_i,x_i,y_i,z_i\leq10$。

思路:

双重的多重背包,第一次我们把运输量作为背包容量,美味度为收益。求出运输$p$的美味度所需的最小运输量,第二次我们把钱作为背包容量,运输量作为收益。求出运输最小运输量的最小费用。

代码:
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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int maxnn = 6e5 + 10;
int n,m,p,dp1[maxnn],need,dp2[maxn],tot1,tot2;
bool flag;
struct food
{
int t,u;
}f[maxn];
struct tool
{
int x,y;
}t[maxn];
int main()
{
// freopen("B.in","r",stdin);
// freopen("B.out","w",stdout);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--)
{
flag = 0;
need = 1e9 + 10;memset(dp1,0,sizeof(dp1));memset(dp2,0,sizeof(dp2));
tot1 = 0;tot2 = 0;
cin >> n >> m >> p;
for(int i = 1 ; i <= n ; ++ i)
{
int t,u,v;
cin >> t >> u >> v;
int k = 1;
while(v >= k)
{
f[++tot1].u = u * k;
f[tot1].t = t * k;
v -= k;
k <<= 1;
}
f[++tot1].u = v * u;f[tot1].t = t * v;//二进制拆分
}
for(int i = 1 ; i <= tot1 ; ++ i)
for(int j = 50000 ; j >= f[i].u ; -- j)//f[i].u * f[i].v ; -- j)
{
dp1[j] = max(dp1[j],dp1[j - f[i].u] + f[i].t);//求出用j的运输量可以运输的最大美味度
if(dp1[j] >= p)need = min(need,j);//如果当前的美味度比需要的大了,就将当前的运输量与最小运输量比较
}
// cout << need << endl;我们就求出了最小运输量了。
for(int i = 1 ; i <= m ; ++ i)
{
int k = 1,x,y,z;
cin >> x >> y >> z;
while(z >= k)
{
t[++tot2].x = x * k;
t[tot2].y = y * k;
z -= k;
k <<= 1;
}
t[++tot2].x = x * z;t[tot2].y = y * z;//二进制拆分
}
/*if(need == 1e9 + 10){
cout << "TAT" << endl;
continue;
}*/
int ans = 50000;
for(int i = 1 ; i <= tot2 ; ++ i)
for(int j = 50000 ; j >= t[i].y ; -- j)
{
dp2[j] = max(dp2[j],dp2[j - t[i].y] + t[i].x);//求出用j的费用可以运输的最大量
if(dp2[j] >= need)ans = min(ans,j);//如果当前的运输量比至少运输量大,就将当前的费用与最小费用比较。
}
if(ans == 50000)cout << "TAT" << endl;
else cout << ans << endl;
}
}