JZOJ 4224 食物

第一眼看，显然是个背包。
但是做题太少抽象不出经典模型……

值得注意的是，一份食物可以被拆成几份分批次运输，达到永远亭后再组装起来。

所以在选车的时候，只要总空间不小于你想装的总体积就可以装。

考虑把问题分成两部分，先求出总大小，再求出总费用。
具体地说： 1. 在总美味度不小于 p 的情况下，最小化总体积。 2. 在总空间不小于总体积的情况下，最小化总费用。

发现两步都可以转化为多重背包，用二进制或者单调队列套路一下就完了。
（其实我 DP 学的少都不会多重背包，刚学二进制套路）

于是又有一个问题：第二步的总体积最大是 200×100×100=2×106，无法作为状态表示。
考虑把状态改成答案即总费用。

另外，此题卡常，吸氧大法好。

代码：

#pragma GCC optimize (2)
#include <cstdio>
#include <cstring>
#include <algorithm>
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);
    }
}