- 有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。
输入格式
- 第一行一个正整数 n(n<=1,000)，接下来 n 行每行三个正整数，分别表示 c[i],a[i],b[i] (c[i]<=1,000,1<=a[i]<b[i]<=109)。
- 下面一行一个正整数 q(q<=1,000,000)，接下来 q 行每行三个非负整数 m,k,s(1<=m<=109,1<=k<=100,000,0<=s<=109)。
输出格式
- 输出 q 行，每行为 "TAK "(yes)或"NIE"(no)，第 i 行对应第 i 此询问的答案。
样例
样例输入
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
样例输出
TAK
NIE
TAK
TAK
NIE
算法分析
- 思维含量蛮高的一个 暴力很好想的
- 先来讲讲暴力的思想: 按照题目描述很容易我们会想到背包问题 直接按照背包问题的格式跑就好了 如果当前物品的a[i] > m || b[i] < m + s 那么就让当前状态背包继承上一状态，不然就可以试着转移 选择最优，每次按照k的容量跑背包，如果最后最大价值是k 那么就表示当前物品可以，裸的板子
- 但是再看复杂度 一个q的询问就如此之大了 显然不能直接跑背包 所以应该怎么做？
- 我们可以把在线询问转化为离线做法 然后就很容易做了
- 对于第一个条件a[i] <= m 我们可以把a[i] 和 m 都升序排列一下
- 关于第二个条件b[i] > m + s 我们可以用一个数组来维护组成数字之和为k的物品中最小的b属性（如果它都满足显然其它的都满足）
- 定义数组f[i] 表示 c属性之和为i的几个物品（而且满足a属性）的b属性的最小值
代码展示
#include<bits/stdc++.h>
using namespace std;
const int maxv = 1e6+10;
int n,m,sum;
int f[maxv * 10];
int ans[maxv * 10];
struct node{
int a,b,c;
}a[maxv];
struct Node{
int m,k,s,id;
}b[maxv * 10];
bool cmp(node a,node b){return a.a < b.a;}
bool Cmp(Node a,Node b){return a.m < b.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].m,&b[i].k,&b[i].s);
b[i].id = i;//记录询问顺序防止排序排乱
}
sort(a + 1,a + n + 1,cmp);
sort(b + 1,b + m + 1,Cmp);
f[0] = 0x3f3f3f3f;
int j = 1;
for(int i = 1;i <= m;++i){
while(j <= n && a[j].a <= b[i].m){
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].k] > b[i].m + b[i].s)ans[b[i].id] = 1;//如果最小的都满足
}
for(int i = 1;i <= m;++i){
if(ans[i])printf("TAK
");
else printf("NIE
");
}
}