【BZOJ2794】[Poi2012]Cloakroom

Description

有n件物品，每件物品有三个属性a[i], b[i], c[i] (a[i]<b[i])。
再给出q个询问，每个询问由非负整数m, k, s组成，问是否能够选出某些物品使得：
1. 对于每个选的物品i，满足a[i]<=m且b[i]>m+s。
2. 所有选出物品的c[i]的和正好是k。

Input

第一行一个正整数n (n<=1,000)，接下来n行每行三个正整数，分别表示c[i], a[i], b[i] (c[i]<=1,000, 1<=a[i]<b[i]<=10^9)。
下面一行一个正整数q (q<=1,000,000)，接下来q行每行三个非负整数m, k, s (1<=m<=10^9, 1<=k<=100,000, 0<=s<=10^9)。

Output

输出q行，每行为TAK (yes)或NIE (no)，第i行对应第i此询问的答案。

Sample Input

5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5

Sample Output

TAK
NIE
TAK
TAK
NIE

题解：容易想到离线处理，先将物品和询问都按A从小到大排序，一边将物品加入背包一边处理询问，但是还有一个限制B，怎么搞？

发现我们的背包是一个判断可行性的背包，也就是说里面的数都是0或1，这其实是一种空间的浪费，我们不妨想办法将这些空间利用起来，作为B的限制。

于是令f[i]表示选出C的和为i时，背包中B值最小的那个物品的B值最大是多少（因为B越大越优，所以我们尽可能将B大的装入背包），然后查询的时候只要判断f[i]是否大于m+s就好了。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int f[1000010];

struct item

{

	int A,B,C;

}p[1010];

int n,m,mk;

struct query

{

	int l,r,v,org;

}q[1000010];

int ans[1000010];

bool cmp1(item a,item b)

{

	return a.A<b.A;

}

bool cmp2(query a,query b)

{

	return a.l<b.l;

}

int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	scanf("%d",&n);

	int i,j,k;

	for(i=1;i<=n;i++)	p[i].C=rd(),p[i].A=rd(),p[i].B=rd();

	scanf("%d",&m);

	for(i=1;i<=m;i++)	q[i].l=rd(),q[i].v=rd(),q[i].r=rd(),mk=max(mk,q[i].v),q[i].org=i;

	sort(p+1,p+n+1,cmp1);

	sort(q+1,q+m+1,cmp2);

	f[0]=1<<30;

	for(i=j=1;i<=m;i++)

	{

		for(;p[j].A<=q[i].l&&j<=n;j++)

		{

			for(k=mk;k>=p[j].C;k--)	f[k]=max(f[k],min(f[k-p[j].C],p[j].B));

		}

		ans[q[i].org]=(q[i].l+q[i].r<f[q[i].v]);

	}

	for(i=1;i<=m;i++)

	{

		if(ans[i])	printf("TAK\n");

		else	printf("NIE\n");

	}

	return 0;

}

巴特西

【BZOJ2794】[Poi2012]Cloakroom 离线+背包