第一眼看，显然是个背包。
但是做题太少抽象不出经典模型……
值得注意的是，一份食物可以被拆成几份分批次运输，达到永远亭后再组装起来。
所以在选车的时候，只要总空间不小于你想装的总体积就可以装。
考虑把问题分成两部分，先求出总大小，再求出总费用。
具体地说： 1. 在总美味度不小于 \(p\) 的情况下，最小化总体积。 2. 在总空间不小于总体积的情况下，最小化总费用。
发现两步都可以转化为多重背包，用二进制或者单调队列套路一下就完了。
（其实我 DP 学的少都不会多重背包，刚学二进制套路）
于是又有一个问题：第二步的总体积最大是 \(200 \times 100 \times 100 = 2 \times 10^6\)，无法作为状态表示。
考虑把状态改成答案即总费用。
另外，此题卡常，吸氧大法好。
代码： 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
using namespace std;
const int N = 200;
const int M = 200;
const int P = 5e4;
const int C = 5e4;
int test;
int n,m,p;
int t[N + 5],u[N + 5],v[N + 5];
int x[M + 5],y[M + 5],z[M + 5];
int f[(P << 1) + 5],ans1;
int g[C + 5],ans2;
int main()
{
scanf("%d",&test);
while(test--)
{
memset(f,0x3f,sizeof f),memset(g,-0x3f,sizeof g);
f[0] = g[0] = 0;
scanf("%d%d%d",&n,&m,&p);
for(register int i = 1;i <= n;++i)
scanf("%d%d%d",t + i,u + i,v + i);
for(register int i = 1;i <= n;++i)
{
int cnt = 1,lim = v[i];
while(cnt < lim)
{
for(register int j = p * 2;j >= cnt * t[i];--j)
f[j] = min(f[j],f[j - cnt * t[i]] + cnt * u[i]);
lim -= cnt,cnt <<= 1;
}
for(register int j = p * 2;j >= lim * t[i];--j)
f[j] = min(f[j],f[j - lim * t[i]] + lim * u[i]);
}
ans1 = 0x3f3f3f3f;
for(register int i = p;i <= p * 2;++i)
ans1 = min(ans1,f[i]);
for(register int i = 1;i <= m;++i)
scanf("%d%d%d",x + i,y + i,z + i);
for(register int i = 1;i <= m;++i)
{
int cnt = 1,lim = z[i];
while(cnt < lim)
{
for(register int j = C;j >= cnt * y[i];--j)
g[j] = max(g[j],g[j - cnt * y[i]] + cnt * x[i]);
lim -= cnt,cnt <<= 1;
}
for(register int j = C;j >= lim * y[i];--j)
g[j] = max(g[j],g[j - lim * y[i]] + lim * x[i]);
}
ans2 = 0;
for(register int i = 1;i <= C;++i)
if(g[i] >= ans1)
{
ans2 = i;
break;
}
if(ans1 == 0x3f3f3f3f || !ans2)
puts("TAT");
else
printf("%d\n",ans2);
}
}