Food Problem
Time Limit: 3000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1510 Accepted Submission(s): 450
Total Submission(s): 1510 Accepted Submission(s): 450
Problem Description
Few days before a game of orienteering, Bell came to a mathematician to solve a big problem. Bell is preparing the dessert for the game. There are several different types of desserts such as small cookies, little grasshoppers and tiny mantises. Every type of dessert may provide different amounts of energy, and they all take up different size of space.
Other than obtaining the desserts, Bell also needs to consider moving them to the game arena. Different trucks may carry different amounts of desserts in size and of course they have different costs. However, you may split a single dessert into several parts and put them on different trucks, then assemble the parts at the game arena. Note that a dessert does not provide any energy if some part of it is missing.
Bell wants to know how much would it cost at least to provide desserts of a total energy of p (most of the desserts are not bought with money, so we assume obtaining the desserts costs no money, only the cost of transportation should be considered). Unfortunately the mathematician is having trouble with her stomach, so this problem is left to you.
Other than obtaining the desserts, Bell also needs to consider moving them to the game arena. Different trucks may carry different amounts of desserts in size and of course they have different costs. However, you may split a single dessert into several parts and put them on different trucks, then assemble the parts at the game arena. Note that a dessert does not provide any energy if some part of it is missing.
Bell wants to know how much would it cost at least to provide desserts of a total energy of p (most of the desserts are not bought with money, so we assume obtaining the desserts costs no money, only the cost of transportation should be considered). Unfortunately the mathematician is having trouble with her stomach, so this problem is left to you.
Input
The first line of input contains a integer
T(T≤10) representing the number of test cases.
For each test case there are three integers n,m,p on the first line (1≤n≤200,1≤m≤200,0≤p≤50000), representing the number of different desserts, the number of different trucks and the least energy required respectively.
The i−th of the n following lines contains three integers ti,ui,vi(1≤ti≤100,1≤ui≤100,1≤vi≤100) indicating that the i−th dessert can provide ti energy, takes up space of size ui and that Bell can prepare at most vi of them.
On each of the next m lines, there are also three integers xj,yj,zj(1≤xj≤100,1≤yj≤100,1≤zj≤100) indicating that the j−th truck can carry at most size of xj , hiring each one costs yj and that Bell can hire at most zj of them.
For each test case there are three integers n,m,p on the first line (1≤n≤200,1≤m≤200,0≤p≤50000), representing the number of different desserts, the number of different trucks and the least energy required respectively.
The i−th of the n following lines contains three integers ti,ui,vi(1≤ti≤100,1≤ui≤100,1≤vi≤100) indicating that the i−th dessert can provide ti energy, takes up space of size ui and that Bell can prepare at most vi of them.
On each of the next m lines, there are also three integers xj,yj,zj(1≤xj≤100,1≤yj≤100,1≤zj≤100) indicating that the j−th truck can carry at most size of xj , hiring each one costs yj and that Bell can hire at most zj of them.
Output
For every test case output the minimum cost to provide the dessert of enough energy in the game arena if it is possible and its cost is no more than
50000. Otherwise, output
TAT on the line instead.
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
Source
2015 ACM/ICPC Asia Regional Changchun Online
当时读题的时候就感觉这题很明显的多重背包，但是感觉条件好多就不敢想……
其实，这个只要把问题拆成两个部分就行了。题意就是，每个点心有一定的能量、空间和数量，然后你的要求是使得总的大于p，然后你可以租一些车来运送这些点心，不同的车有不同的价格、容量和数量，问你在满足能量总数大于p的情况下，最小要花费多少。
确实如果看成一个整体去考虑，确实不好dp。于是拆成两个独立的问题，首先，总能量大于p最少需要多少空间，然后对于这个最少的空间，我又需要花费最小多少代价能够把这些东西装完。
如果这么考虑的话，问题就变成了两个多重背包问题。但是我们发现，不管是点心还是车，由于又有数量限制，所以如果用普通的多重背包三个for，那么显然会超时。这个是一个经典的问题，但是我之前一直没有接触……就是用二进制优化。大致意思就是例如数量为7，其二进制而111，那么我可以拆成三个背包，大小为原来的1倍的，2倍的和4倍的，然后做01背包即可。为什么这样可以呢？因为我们发现，用1、2和4完全可以组成1~7之内的所有数字，做01背包等价于考虑了所有的情况。这样由于01背包的复杂度是O(VN)的，所以可以解决这个问题。
当我们求出来最小的空间的时候，我开始的想法是第二部分也是按照枚举空间、和背包这种形式其做，但是遗憾的发现，这个空间可以很大，最多可以到200W，不可接受。但是接着又看见价值最大值是50000，于是我们可以反过来考虑，计算某一价格最大能够装下多少空间的物品。dp的转移方程大致对应改一下即可。具体见代码：
#include<bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
#define N 101000
using namespace std;
int dp[N],w[N],p[N],n,m,val,num;
int main()
{
int T_T;
cin>>T_T;
while(T_T--)
{
scanf("%d%d%d",&n,&m,&val);
num=0;
for(int i=1;i<=n;i++)
{
int c,v,k,j;
scanf("%d%d%d",&v,&c,&k);
for(j=1;k;j<<=1) //二进制拆分
{
int t=min(j,k);
w[++num]=t*c;
p[num]=t*v; k-=t;
}
}
memset(dp,INF,sizeof(dp));
dp[0]=0;
for(int j=1;j<=num;j++) //01背包求最小空间
for(int i=val+100;i>=p[j];i--)
dp[i]=min(dp[i],dp[i-p[j]]+w[j]);
int space=INF;
for(int i=val;i<=val+100;i++)
space=min(space,dp[i]);
num=0;
for(int i=1;i<=m;i++)
{
int c,v,k,j;
scanf("%d%d%d",&c,&v,&k); //注意与上面有点不同，c与v交换了位置
for(j=1;k;j<<=1)
{
int t=min(j,k);
w[++num]=t*c;
p[num]=t*v; k-=t;
}
}
memset(dp,0,sizeof(dp));
for(int j=1;j<=num;j++)
for(int i=50000;i>=p[j];i--)
dp[i]=max(dp[i],dp[i-p[j]]+w[j]); //这里求某一价值最大能够取到的空间
int ans=INF;
for(int i=1;i<=50000;i++)
if (dp[i]>=space) {ans=i;break;} //如果最大能够取到的空间大于需要的空间，那么这个价值就是答案
if (ans!=INF) printf("%d\n",ans);
else puts("TAT");
}
}