POI2012 Cloakroom
题目描述（搬自洛谷）
有 \(n\) 件物品，每件物品有三个属性 \(a_i, b_i, c_i\ (a_i<b_i)\)。
再给出 \(q\) 个询问，每个询问由非负整数 \(m, k, s\) 组成，问是否能够选出某些物品使得：
- 对于每个选的物品 \(i\)，满足 \(a_i\le m\) 且 \(b_i>m+s\)。
- 所有选出物品的 \(c_i\) 的和正好是 \(k\)。
\(1\le n\le 1000\)，\(1\le a_i<b_i\le 10^9\)，\(1\le c_i\le 1000\)。
\(1\le q\le 10^6\)，\(1\le m\le 10^9\)，\(1\le k\le 10^5\)，\(0\le s\le 10^9\)。
思路
注意到每个物品有三个属性，于是将其分开考虑：
-
对于 \(c_i\) 的限制，考虑 01 背包。
-
对于 \(a_i\) 的限制，考虑离线、放到时间维度上做。
具体地：我们称对于物品 \(i\) 进行背包 DP 为「将 \(i\) 添加进 DP 数组」。
将物品按 \(a_i\) 从小到大排序，依次添加进 DP 数组。若在某一时刻所有 \(a_i \le m\) 的物品 \(i\) 都被添加了，那么便可回答当前询问。将询问按 \(m\) 从小到大排序即可。
-
发现 01 背包的 DP 值是布尔，信息非常有限；于是对于 \(b_i\) 的限制，考虑将其塞进 DP 的值里。
设被选的物品集合为 \(S\)。注意到，\(\forall i \in S\) 都有 \(b_i > m+s\)，等价于 \(\min \{b_i\} > m+s\)。
设 \(f(i,j)\) 表示前 \(i\) 个物品，正好凑出 \(j\) 的方案中，\(\min b_i\) 的最大值。
此部分时间复杂度为 \(\mathcal O(n \cdot \max k)\)，使用滚动或压维技巧，即可将空间复杂度优化为 \(\mathcal O(\max k)\)。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5, M=1e6+5, K=2e5+5;
int n,q,f[K],ans[M];
struct item{
int a,b,c;
bool operator<(const item &_) const{
return a<_.a;
}
}a[N];
struct qry{
int L,R,k,id;
bool operator<(const qry &_) const{
return L<_.L;
}
}b[M];
template<typename T>
inline T max_eq(T &x,T y){
return x= x>y? x:y;
}
void dp(int i){
for(int j=1e5;j>=0;--j)
max_eq(f[j+a[i].c],min(f[j],a[i].b));
}
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",&q);
for(int i=1;i<=q;++i){
int range;
scanf("%d%d%d",&b[i].L,&b[i].k,&range);
b[i].R=b[i].L+range, b[i].id=i;
}
sort(a+1,a+n+1);
sort(b+1,b+q+1);
f[0]=INT_MAX;
for(int i=1,x=0;i<=q;++i){
while(x<n&&a[x+1].a<=b[i].L) dp(++x);
ans[b[i].id]= f[b[i].k]>b[i].R;
}
for(int i=1;i<=q;++i) puts(ans[i]? "TAK":"NIE");
return 0;
}