洛谷P3537 [POI2012]SZA-Cloakroom(背包)

时间:2021-06-02 08:41:19

传送门

蠢了……还以为背包只能用来维护方案数呢……没想到背包这么神奇……

我们用$dp[i]$表示当$c$的和为$i$时,所有的方案中使得最小的$b$最大时最小的$b$是多少

然后把所有的点按照$a$排序,询问按照$m$排序

然后跑一遍背包,如果$dp[q[i].k]>q[i].s+q[i].m$,即存在方案使得$c$的和为$q[i].k$且所有的$b$都大于$q[i].s+q[i].m$,那么这个询问就是可行的

但这个时间复杂度……我实在不明白为什么它能跑出来……而且好像还很快的样子……明明理论上得跑11天才能出答案……

 //minamoto
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,:;}
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=,M=1e6+;
struct node{
int a,b,c;
inline bool operator <(const node &s)const
{return a<s.a;}
}p[N];
struct query{
int m,k,s,id;
inline bool operator <(const query &b)const
{return m<b.m;}
}q[M];
int dp[],n,m,ans[M];
int main(){
// freopen("testdata.in","r",stdin);
n=read();
for(int i=;i<=n;++i)
p[i].c=read(),p[i].a=read(),p[i].b=read();
sort(p+,p++n);
m=read();
for(int i=;i<=m;++i)
q[i].m=read(),q[i].k=read(),q[i].s=read(),q[i].id=i;
sort(q+,q++m);dp[]=inf;
for(int i=,j=;i<=m;++i){
while(j<=n&&p[j].a<=q[i].m){
for(int k=;k>=p[j].c;--k)
cmax(dp[k],min(dp[k-p[j].c],p[j].b));
++j;
}
ans[q[i].id]=dp[q[i].k]>q[i].m+q[i].s;
}
for(int i=;i<=m;++i) puts(ans[i]?"TAK":"NIE");
return ;
}