P3537 [POI2012]SZA

2018-11-01 16:05:52


题意:有 $n$ 个物品,每个物品有三个属性 $:a_i,b_i,c_i$

   多组询问,每次询问有三个参数 $:m,k,s$

   问能否选出一些物品使得 $:a_i<=m$ 且 $b_i>m+s$ ,选出的物品 $c_i$ 之和等于 $k$

    $1<=a_i,b_i<10^9,1<=c_i<=10^3,1<=k<=10^5,1<=q<=10^6$


$emm$ ,很明显要离线处理

将物品按 $a$ 从小到大排序,询问按 $m$ 从小到大排序

这样从前往后扫可以保证 $a_i<=m$

因为 $k$ 比较小,考虑背包

$f[k]$ 表示选择的物品 $c_i$ 之和为 $k$ 时,最小的 $b_i$ 的最大值

转移和普通背包相同,注意倒序循环

如果一个询问满足 $f[k]>m+s$ ,那么就是有解的

注意 $f[0]$ 要设成 $INF$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=1005,M=1e6+5,maxn=1e5+5,inf=1e9;
struct node
{
    int a,b,c;
    inline friend bool operator < (node a,node b) {return a.a<b.a;}
}p[N];
struct Q
{
    int up,k,s,id;
    inline friend bool operator < (Q a,Q b) {return a.up<b.up;}
}q[M];
int n,m,ans[M],f[maxn];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
int main()
{
    n=read();
    for (reg int i=1;i<=n;i++) p[i].c=read(),p[i].a=read(),p[i].b=read();
    sort(p+1,p+n+1); m=read();
    for (reg int i=1;i<=m;i++) q[i].up=read(),q[i].k=read(),q[i].s=read(),q[i].id=i;
    sort(q+1,q+m+1); f[0]=inf;
    for (reg int i=1,now=1;i<=m;i++)
    {
        while (p[now].a<=q[i].up&&now<=n)
        {
            for (reg int j=maxn-5;j>=p[now].c;j--)
              f[j]=max(f[j],min(f[j-p[now].c],p[now].b));
            ++now;
        }
        if (f[q[i].k]>q[i].up+q[i].s) ans[q[i].id]=1;
    }
    for (reg int i=1;i<=m;i++) puts(ans[i]?"TAK":"NIE");
    return 0;
}