首先，单独处理每个询问复杂度显然不可承受，还是考虑通过排序使得限制更容易达到：按照$a$将物品排序，按照$m$将询问排序，这样肯定是要不断添加物品才能达到要求，顺着做一遍就行了
然后发现$b$的限制仍然不好满足，但是我们的可行性dp的数组只记录了是否可行，还有利用的余地，那么以$dp[i]$记录达到$i$的所有方案中最小的$b$的最大值，查询的时候就可以判定了
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1005,M=1000005,K=100005,inf=1e9; 6 struct a{int cc,aa,bb;}obj[N]; 7 struct b{int m,k,s,id;}qry[M]; 8 int n,T,last,dp[K],outp[M]; 9 bool cmp1(a x,a y) 10 { 11 return x.aa<y.aa; 12 } 13 bool cmp2(b x,b y) 14 { 15 return x.m<y.m; 16 } 17 int main() 18 { 19 scanf("%d",&n); 20 for(int i=1;i<=n;i++) 21 scanf("%d%d%d",&obj[i].cc,&obj[i].aa,&obj[i].bb); 22 scanf("%d",&T); 23 for(int i=1;i<=T;i++) 24 scanf("%d%d%d",&qry[i].m,&qry[i].k,&qry[i].s),qry[i].id=i; 25 sort(obj+1,obj+1+n,cmp1),sort(qry+1,qry+1+T,cmp2); dp[0]=inf,last=1; 26 for(int i=1;i<=T;i++) 27 { 28 while(last<=n&&obj[last].aa<=qry[i].m) 29 { 30 for(int j=K-1;j>=obj[last].cc;j--) 31 dp[j]=max(dp[j],min(dp[j-obj[last].cc],obj[last].bb)); 32 last++; 33 } 34 outp[qry[i].id]=(dp[qry[i].k]>qry[i].m+qry[i].s); 35 } 36 for(int i=1;i<=T;i++) 37 outp[i]?printf("TAK "):printf("NIE "); 38 return 0; 39 }