P3537 [POI2012]SZA

题意：有$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; } ```