自动搬运

查看原文

来自洛谷，原作者为

	MloVtry **

搬运于2025-08-24 21:49:58，当前版本为作者最后更新于2018-03-02 16:43:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

背包。

先把物品按照a排个序，询问离线，按照m排个序。

这样就可以用增添物品的方法让$a_i\leq m$这个条件合法。设$f_k$表示当一些物品的$\sum C_i=k$时，其中$b_i$的最小值的最大化值。

emmmm....就是让这个$b_i$的最小值尽可能大。

DP一下即可。

代码

#include<bits/stdc++.h>
#define N 1200000
using namespace std;
struct node
{
	int a,b,c,id;
}a[1010],b[N];
int f[100010],ans[N];
bool comp(node aa,node bb)
{
	return aa.a<bb.a;
}
int n,m;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d%d%d",&a[i].c,&a[i].a,&a[i].b);
	scanf("%d",&m);
	for(int i=1;i<=m;++i) scanf("%d%d%d",&b[i].a,&b[i].b,&b[i].c),b[i].id=i;
	sort(a+1,a+n+1,comp);
	sort(b+1,b+m+1,comp);
	int j=1;f[0]=1e9;
	for(int i=1;i<=m;++i)
	{
		while(j<=n&&a[j].a<=b[i].a)
		{
			for(int k=100000;k>=a[j].c;--k)
			f[k]=max(f[k],min(f[k-a[j].c],a[j].b));
			j++;
		}
		if(f[b[i].b]>b[i].a+b[i].c) ans[b[i].id]=1;
	}
	for(int i=1;i<=m;++i) puts(ans[i]?"TAK":"NIE");
	return 0;
}