题目大意
有 \(n\) 件物品,每件物品有三个属性 \(a_i, b_i, c_i (a_i < b_i)\)。
再给出 \(q\) 个询问,每个询问由非负整数 \(m, k, s\)组成,问是否能够选出某些物品使得:
-
对于每个选的物品 \(i\),满足 \(a_i \leq m\) 且 \(b_i > m + s\)。
-
所有选出物品的 \(c\) 的和正好是 \(k\)。
分析
如果没有 \(a_i \leq m\) 且 \(b_i > m + s\) 的条件,明显是个背包。
然而有这两个限制就不好办了。我们可以先把询问离线下来,按照 \(m\) 排序(当然 \(a_i\) 也要排序),这样就把二维偏序转化成了一维。(大概可以这样理解)。
接下来,我们需要判断在 \(\forall a_i \leq m\) 和 \(\sum c_i = k\) 满足后 \([\forall b_i > m + s]\) 是否成立。
这个也很好办。我们只需要将背包状态设为 \(f_i\) 表示背包容积(即放入的 \(c\))大小为 \(i\) 时 \(b\) 的最小值的最大值。只要这个最小值比 \(m + s\) 大,那么就一定合法,否则一定不合法。
最后一定注意输入顺序是 \(c, a, b\) 而不是 \(a, b, c\)!
参考代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1010, M = 1000010;
struct Node {
int a, b, c;
bool operator < (const Node& tmp)const {
return a < tmp.a;
}
}p[N];
struct Queries {
int m, k, s, id;
bool operator < (const Queries& tmp)const {
return m < tmp.m;
}
}q[M];
int f[100010];
int n, m;
bool ans[M];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
scanf("%d%d%d", &p[i].c, &p[i].a, &p[i].b);
sort(p + 1, p + n + 1);
scanf("%d", &m);
for (int i = 1; i <= m; i ++ )
scanf("%d%d%d", &q[i].m, &q[i].k, &q[i].s),
q[i].id = i;
sort(q + 1, q + m + 1); // 将限制 A 消除
int now = 1; f[0] = 0x3f3f3f3f;
for (int i = 1; i <= m; i ++ ) {
while (now <= n && p[now].a <= q[i].m) {
for (int j = 100000; j >= p[now].c; j -- )
f[j] = max(f[j], min(f[j - p[now].c], p[now].b)); // 背包满足限制 C
now ++ ;
}
if (f[q[i].k] > q[i].m + q[i].s) ans[q[i].id] = true; // 判断限制 B 是否满足
}
for (int i = 1; i <= m; i ++ )
puts(ans[i] ? "TAK" : "NIE");
return 0;
}
标签:tmp,now,const,leq,POI2012,题解,Cloakroom,int,include
From: https://www.cnblogs.com/LcyRegister/p/17006672.html