解题：POI 2012 Cloakroom

首先，单独处理每个询问复杂度显然不可承受，还是考虑通过排序使得限制更容易达到：按照$a$将物品排序，按照$m$将询问排序，这样肯定是要不断添加物品才能达到要求，顺着做一遍就行了

然后发现$b$的限制仍然不好满足，但是我们的可行性dp的数组只记录了是否可行，还有利用的余地，那么以$dp[i]$记录达到$i$的所有方案中最小的$b$的最大值，查询的时候就可以判定了

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,M=,K=,inf=1e9;

 struct a{int cc,aa,bb;}obj[N];

 struct b{int m,k,s,id;}qry[M];

 int n,T,last,dp[K],outp[M];

 bool cmp1(a x,a y)

 {

     return x.aa<y.aa;

 }

 bool cmp2(b x,b y)

 {

     return x.m<y.m;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

         scanf("%d%d%d",&obj[i].cc,&obj[i].aa,&obj[i].bb);

     scanf("%d",&T);

     for(int i=;i<=T;i++)

         scanf("%d%d%d",&qry[i].m,&qry[i].k,&qry[i].s),qry[i].id=i;

     sort(obj+,obj++n,cmp1),sort(qry+,qry++T,cmp2); dp[]=inf,last=;

     for(int i=;i<=T;i++)

     {

         while(last<=n&&obj[last].aa<=qry[i].m)

         {

             for(int j=K-;j>=obj[last].cc;j--)

                 dp[j]=max(dp[j],min(dp[j-obj[last].cc],obj[last].bb));

             last++;

         }

         outp[qry[i].id]=(dp[qry[i].k]>qry[i].m+qry[i].s);

     }

     for(int i=;i<=T;i++)

         outp[i]?printf("TAK\n"):printf("NIE\n");

     return ;

 }

巴特西

解题：POI 2012 Cloakroom

最新文章

热门文章