[背包问题][二进制优化] Jzoj P4224 食物

阅读量：5321 次

发布时间：2019-06-14

本文共 1620 字，大约阅读时间需要 5 分钟。

Description

Input

Output

Sample Input

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

Sample Output

4 14 12 TAT

Data Constraint

题解

题目大意：有n种食物，和m种交通工具，问在费用不超过50000和美味度大于等于p时，需要的最少的运输费

这显然是一个多重背包问题

设f[i]为食物大小为i的时候所能得到的最大美味度，转移显然，f[i]=min(f[i-u]+t)

再设g[i]为费用为i的时候所能得到的最大运输量，转移也显然，g[i]=min(g[i-y]+x)

最后的话，然后使f[g[i]]>=p的时候，ans取一个min就好了

这样跑的话，显然会T的飞起，考虑一下怎么优化

这题有三种优化：优先队列、二进制优化、吸氧优化（由于博主过于蒟蒻在这里只讲二进制优化）

二进制优化其实就是将其变成1、2、4、8、16....的形式

然后我们可以发现，这样的话，既可以将所有的状态给表示出来，也可以很有效的减少循环状态数、数组的大小

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define N 50010 5 using namespace std; 6 int n,m,p,ans,T,f[N],g[N]; 7 void dp(int x,int y) { for (int i=20000;i>=x;i--) f[i]=max(f[i],f[i-x]+y); } 8 void dp1(int x,int y) { for (int i=50000;i>=x;i--) g[i]=max(g[i],g[i-x]+y); } 9 int main()10 {11     scanf("%d",&T);12     while (T--)13     {14         scanf("%d%d%d",&n,&m,&p),memset(f,0,sizeof(f)),memset(g,0,sizeof(g)); 15         for (int i=1,t,u,w;i<=n;i++)16         {17             scanf("%d%d%d",&t,&u,&w);18             for (int j=1;j<=w;w-=j,j*=2) dp(u*j,t*j);19             if (w) dp(u*w,t*w);20         }21         for (int i=1,x,y,k;i<=m;i++)22         {23             scanf("%d%d%d",&x,&y,&k);24             for (int j=1;j<=k;k-=j,j*=2) dp1(y*j,x*j);25             if (k) dp1(y*k,x*k);26         }27         ans=0;28         for (int i=1;i<=50000;i++) if (f[g[i]]>=p) { ans=i; break;}29         if (ans) printf("%d\n",ans); else printf("TAT\n");30     }31 }