链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2794
数据生成器：http://paste.ubuntu.com/23946550/
神犇题解：http://trinklee.blog.163.com/blog/static/23815806020149855817630
题解
这个题目假如没有A[]和B[]的限制的话，就是一个正常的背包
然而有了这两个东西，而且复杂度要求O(1)询问，这样我就不会了 QwQ
考虑传统背包的局限性：
1）添加物品的顺序没有限制，但实际上是浪费了一些性质
2）DP的是一个bool数组，只记录是否可以凑出，这样实际上也是浪费了信息
于是考虑离线，将询问的m和物品的a[]都按照升序排好序
然后规定f[i][j]表示用前i个物品，凑出j的b[]的最小值的最大值
之后对于每个询问，A[]可以用i来限制，B[]可以直接判断
于是边DP边回答询问的话
就可以O(1)处理所有询问辣！
★,°:.☆(￣▽￣)/$:.°★ 。
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1000+9;
const int M = 1000000+9;
const int INF = 100000;
struct Event{
int a,b,c,d;
inline Event() {}
inline Event(int _a, int _b, int _c):a(_a),b(_b),c(_c) {}
inline bool operator < (const Event &B) const {return a < B.a;}
}t[N],q[M];
int f[M],arr[M+N<<1],vout[M],tot,n,m,mx;
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
int main() {
n = read();
for (int i=1,a,b,c;i<=n;i++) {
a = read(); b = read(); c = read();
arr[++tot] = c; arr[++tot] = b;
t[i] = Event(b, c, a);
}
m = read();
for (int i=1,a,b,c;i<=m;i++) {
a = read(); b = read(); c = read() + a;
arr[++tot] = a; arr[++tot] = c;
q[i] = Event(a, c, b);
q[i].d = i;
}
sort(arr+1, arr+1+tot);
tot = unique(arr+1, arr+1+tot) - arr - 1;
for (int i=1;i<=n;i++) {
t[i].a = lower_bound(arr+1, arr+1+tot, t[i].a) - arr;
t[i].b = lower_bound(arr+1, arr+1+tot, t[i].b) - arr;
mx = max(mx, t[i].a);
}
for (int i=1;i<=m;i++) {
q[i].a = lower_bound(arr+1, arr+1+tot, q[i].a) - arr;
q[i].b = lower_bound(arr+1, arr+1+tot, q[i].b) - arr;
q[i].a = min(q[i].a, mx);
}
sort(t+1, t+1+n);
sort(q+1, q+1+m);
f[0] = 1e9;
for (int j=1,p1=1;j<=m;j++) {
for (;t[p1].a<=q[j].a&&p1<=n;p1++) {
for (int i=INF-t[p1].c,to=INF;i>=0;i--,to--) {
f[to] = max(f[to], min(f[i], t[p1].b));
}
}
vout[q[j].d] = f[q[j].c] > q[j].b;
}
for (int i=1;i<=m;i++) {
if (vout[i]) puts("TAK");
else puts("NIE");
}
return 0;
}
