有n件物品，每件物品有三个属性a[i], b[i], c[i] (a[i]<b[i])。
再给出q个询问，每个询问由非负整数m, k, s组成，问是否能够选出某些物品使得：
1. 对于每个选的物品i，满足a[i]<=m且b[i]>m+s。
2. 所有选出物品的c[i]的和正好是k。
有n件物品，每件物品有三个属性a[i], b[i], c[i] (a[i]<b[i])。
再给出q个询问，每个询问由非负整数m, k, s组成，问是否能够选出某些物品使得：
1. 对于每个选的物品i，满足a[i]<=m且b[i]>m+s。
2. 所有选出物品的c[i]的和正好是k。
第一行一个正整数n (n<=1,000)，接下来n行每行三个正整数，分别表示c[i], a[i], b[i] (c[i]<=1,000, 1<=a[i]<b[i]<=10^9)。
下面一行一个正整数q (q<=1,000,000)，接下来q行每行三个非负整数m, k, s (1<=m<=10^9, 1<=k<=100,000, 0<=s<=10^9)。
输出q行，每行为TAK (yes)或NIE (no)，第i行对应第i此询问的答案。
先看数据范围，发现q非常的大，所以想到离线处理。
如果离线处理，可以把a的这个条件直接去掉，只需用b和c来DP。
然后就非常简单了。时间复杂度$O(qlogq+nk)$
1 #include<cstdio> 2 #include<algorithm> 3 #define N 1005 4 #define M 100010 5 #define Q 1000100 6 using namespace std; 7 inline int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 11 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 12 return x*f; 13 } 14 int n,q,f[M]={1e9},ans[Q],maxn; 15 struct node{int a,b,c,id;}a[N],b[Q]; 16 bool operator<(node x,node y){return x.a<y.a;} 17 int main() 18 { 19 n=read(); 20 for(int i=1;i<=n;i++) 21 a[i].c=read(),a[i].a=read(),a[i].b=read(); 22 sort(a+1,a+n+1); 23 q=read(); 24 for(int i=1;i<=q;i++) 25 b[i].a=read(),b[i].c=read(),b[i].b=read(), 26 b[i].id=i,maxn=max(maxn,b[i].c); 27 sort(b+1,b+q+1); 28 for(int i=1,j=1;i<=q;i++) 29 { 30 while(j<=n&&a[j].a<=b[i].a) 31 { 32 for(int k=maxn;k>=a[j].c;k--) 33 f[k]=max(f[k],min(f[k-a[j].c],a[j].b)); 34 j++; 35 } 36 ans[b[i].id]=(f[b[i].c]>b[i].a+b[i].b); 37 } 38 for(int i=1;i<=q;i++) 39 puts(ans[i]?"TAK":"NIE"); 40 }
原文：http://www.cnblogs.com/xuruifan/p/5189495.html
