【JZOJ A组】食物

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

思路

不妨把这题分为两个问题

1. 达到p美味度所需的最小空间
2. 达到上面所需最小空间要多少钱

第一个可以用背包解决，第二个则不能。

不妨改一下：用一定的钱达到的最大空间是多少，这样就可以啦！

用二进制拆分+吸氧气就可以过啦

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#pragma GCC optimize(2)
using namespace std;
const int maxn=5e4+177;
struct node
{
	int v,w;
}a[maxn],b[maxn];
int n,m,p,f[maxn],tot1,tot2,T;
void init()
{
	scanf("%d%d%d",&n,&m,&p);
	tot1=tot2=0;
	for(int i=1; i<=n; i++)
	{
		int t,x,y,z=1;
		scanf("%d%d%d",&t,&x,&y);
		while(y)
		{
			if(y>=z)
			{
				y-=z;
				a[++tot1].v=z*t; a[tot1].w=z*x;
				z<<=1;
			}else
			{
				z=y; y=0;
				a[++tot1].v=z*t; a[tot1].w=z*x;
			}
		}
	}
	for(int i=1; i<=m; i++)
	{
		int t,x,y,z=1;
		scanf("%d%d%d",&t,&x,&y);
		while(y)
		{
			if(y>=z)
			{
				y-=z;
				b[++tot2].v=z*t; b[tot2].w=z*x;
				z<<=1;
			}
			else if(y)
			{
				z=y; y=0;
				b[++tot2].v=z*t; b[tot2].w=z*x;
			}
		}
	}
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		init();
//		if(T==4&&n==200&&m==200&&p==50000)
		memset(f,0x3f,sizeof(f)); f[0]=0;
		for(int i=1; i<=tot1; i++)
		{
			for(int j=p+100; j>=a[i].v; j--)
				f[j]=min(f[j],f[j-a[i].v]+a[i].w);
			if(a[i].v>p) 
				for(int j=p+100; j>=0; j--) f[j]=min(f[j],a[i].w);
		}
		int pp=f[p];
		memset(f,0,sizeof(f));
		for(int i=1; i<=tot2; i++)
		{
			for(int j=maxn-77; j>=b[i].w; j--) f[j]=max(f[j],f[j-b[i].w]+b[i].v);
		}
		int ans=0x3f3f3f3f;
		for(int i=0; i<=maxn-77; i++) if(pp<=f[i])
		{
			ans=i; break;
		}
		if(ans!=0x3f3f3f3f) printf("%d\n",ans); else printf("TAT\n");
	}
}