1.26 4224-食物

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^2会在这道题里会超时，这时需要nlogn的背包的时间复杂度

#include <bits/stdc++.h>
 using namespace std;
 int n,m,p,test,t,u,v,x,y,z,ans,f[100001],g[100001];
 int main()
 {
 	 	cin>>test;
 	 	while (test>0)
 	 	{
 	 		test--;
 	 		ans=0;
 	 		cin>>n>>m>>p;
 	 		memset(f,0,sizeof(f)),memset(g,0,sizeof(g)); 
 	 		for (int i=1;i<=n;i++)
 	 		{
 	 			cin>>t>>u>>v;
 	 			for (int j=1;j<=v;v-=j,j*=2) 
 	 			  for (int k=20000;k>=u*j;k--)
 	 			    f[k]=max(f[k-(u*j)]+(t*j),f[k]);
 	 			if (v)  
 	 			for (int k=20000;k>=u*v;k--)
 	 			    f[k]=max(f[k-(u*v)]+(t*v),f[k]);
			} 	 		
 	 		for (int i=1;i<=m;i++)
 	 		{
 	 			cin>>x>>y>>z;
 	 			for (int j=1;j<=z;z-=j,j*=2)
 	 			  for (int k=50000;k>=j*y;k--)
 	 			    g[k]=max(g[k],g[k-(y*j)]+(x*j));
 	 			if (z)  
 	 			   for (int k=50000;k>=z*y;k--)
 	 			     g[k]=max(g[k],g[k-(y*z)]+(x*z));
			  }
 	 		for (int i=1;i<=50000;i++)
 	 		if (f[g[i]]>=p) 
 	 		{
 	 			ans=i;
 	 			break;
			  }
 	 		if (ans==0)
 	 		  cout<<"TAT"<<endl;
 	 		  else cout<<ans<<endl;
		  }
 }