【洛谷】P3537 [POI2012]SZA-Cloakroom

题目描述
有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此询问的答案。

输入样例

输出样例

TAK

NIE

TAK

NIE

分析

看起来像个背包，但是它是有限制的。

所以这并不是难不难的问题，它就是那种，被大佬们称作‘有限制的背包问题’的东西

由于物品无序，所以对于第一个限制，可以按a从小到大排序，一个一个放入背包并记录，回答时直接二分一下位置就好了。

我们发现这个题目比以往的题目少了一条限制，即物品的个数。

而且k很小，这个题只需要回答yes和no

所以直接考虑dp[i][j]，表示选前i个物品c的和为j时，所用物品的b的最大值，直接转移即可

这样的话，对于每个问题，

第一个限制直接二分得到a中最后一个小于等于m的位置i

第二个直接看dp[i][k]是否大于m+s，大于则输出yes，反之输出no。

但发现好像内存开不下，所以离线处理询问，再像完全背包一样去dp，一边做一边记录答案

代码如下，感觉细节贼多。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

struct node{int m,k,s,id;}que[];

int n,Q,a[maxn],b[maxn],c[maxn],q[maxn],w[maxn],ans[],dp[];

bool cmp(int x,int y){return a[x]<a[y];}

bool cmp1(node a,node b){return a.m<b.m;}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d%d%d",&c[i],&a[i],&b[i]),w[i]=a[q[i]=i];

    scanf("%d",&Q);for(int i=;i<=Q;i++)scanf("%d%d%d",&que[i].m,&que[i].k,&que[i].s),que[i].id=i;

    sort(w+,w++n);sort(q+,q++n,cmp);sort(que+,que++Q,cmp1);

    int K=;

    dp[]=1e9;

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

    {

        while(K<=Q&&que[K].m<w[i])ans[que[K].id]=(dp[que[K].k]>que[K].m+que[K].s),K++;

        sum+=c[q[i]];sum=min(sum,);

        for(int j=sum;j>=c[q[i]];j--)

        dp[j]=max(dp[j],min(dp[j-c[q[i]]],b[q[i]]));

    }

    while(K<=Q)ans[que[K].id]=(dp[que[K].k]>que[K].m+que[K].s),K++;

    for(int i=;i<=Q;i++)if(ans[i])puts("TAK");else puts("NIE");

}

巴特西

【洛谷】P3537 [POI2012]SZA-Cloakroom

最新文章

热门文章