[POI2012] Cloakroom - Solution

Welcome ^.^ / 2024-11-07 / 原文

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;
}