有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此询问的答案。
#include<set> #include<map> #include<cmath> #include<stack> #include<queue> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct node { int a; int b; int c; int id; }x[1010],y[1200000]; int f[100010]; int ans[1200000]; bool cmp(node x,node y) { return x.a<y.a; } int n,m; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&x[i].c,&x[i].a,&x[i].b); } scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&y[i].a,&y[i].b,&y[i].c); y[i].id=i; } sort(x+1,x+n+1,cmp); sort(y+1,y+m+1,cmp); int num=1; f[0]=1e9; for(int i=1;i<=m;i++) { while(num<=n&&x[num].a<=y[i].a) { for(int k=100000;k>=x[num].c;--k) { f[k]=max(f[k],min(f[k-x[num].c],x[num].b)); } num++; } if(f[y[i].b]>y[i].a+y[i].c) { ans[y[i].id]=1; } } for(int i=1;i<=m;i++) { ans[i]?printf("TAK\n"):printf("NIE\n"); } }
BZOJ2794[Poi2012]Cloakroom——离线+背包
原文:https://www.cnblogs.com/Khada-Jhin/p/9633107.html