Description：

有 $n$ 件物品，每件物品有三个属性 $a[i], b[i], c[i] (a[i]<b[i])$ 。再给出 $q$ 个询问，问是否能够选出某些物品使得：

对于每个选的物品 $i$ ，满足 $a[i]\leqslant m$ 且， $b[i]>m+s$ 所有选出物品的 $c[i]$ 的和正好是 $k$ 。

$1\leqslant n\leqslant 10^3,1\leqslant k_i\leqslant10^5,1\leqslant q\leqslant10^9$

Solution：

首先一个很显然的思路是把询问离线，把所有物品按 $a[i]$ 排序然后对 $c[i]$ 做背包，这样可以用一个可达性 $DP$ ，但是 $b[i]$ 非常不好处理，不过其实这也是动态规划的一个非常经典的处理方法，就是把本来记在状态里的记录在值里，这里既然是一个可达性 $DP$ ，那不如把 $b$ 记录在 $f$ 里，即设 $f[i]$ 表示获得 $i$ 的体积 $b_i$ 的最小值最大是多少，那转移就是 $f[j]=\max(f[j],\min(f[j-c[i]],b[i]))$ 。最后判断一下 $f[k]$ 是否 $>m+s$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1010

struct item

{

	int a,b,c;

}s[MAXN];

bool cmp_a(item x,item y){return x.a < y.a;}

#define MAXQ 1000010

struct query

{

	int m,k,s;

	int id,ans;

}q[MAXQ];

bool cmp_m(query x,query y){return x.m < y.m;}

bool cmp_id(query x,query y){return x.id < y.id;}

#define MAX 100000

int f[MAX + 1];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d%d%d",&s[i].c,&s[i].a,&s[i].b);

	sort(s + 1,s + 1 + n,cmp_a);

	scanf("%d",&m);

	for(int i = 1;i <= m;++i)scanf("%d%d%d",&q[i].m,&q[i].k,&q[i].s);

	for(int i = 1;i <= m;++i)q[i].id = i;

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

	f[0] = 0x3f3f3f3f;

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

	{

		while(i <= n && s[i].a <= q[j].m)

		{

			for(int k = MAX;k >= s[i].c;--k)

			{

				f[k] = max(f[k],min(f[k - s[i].c],s[i].b));

			}

			++i;

		}

		if(f[q[j].k] > q[j].m + q[j].s)q[j].ans = 1;

	}

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

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

	{

		if(q[i].ans)puts("TAK");

		else puts("NIE");

	}

	return 0;

}