Cloakroom

Cloakroom ( dp\(\star\star?\))

• 时限：\(1s\) 内存：\(256M\)

Descrption

• 有 \(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\) 。

Input

• 第一行一个正整数 \(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)\)。

Output

• 输出 \(q\) 行，每行为 "$TAK \(" (\)yes\()或"\)NIE\(" (\)no$)，第 \(i\) 行对应第 \(i\) 此询问的答案。

Sample Input

5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5

Sample Output

TAK
NIE
TAK
TAK
NIE

Hint

• 来源：\(luogup3537\)

分析

• 此题不太好想，不过只考虑条件 \(2\) ，我们很容易能想到 \(0/1\) 背包，关键问题是如何解决条件 \(1\) 的问题。
• 对于条件 \(a[i]\le m\) ，我们可以把数据对 \(a\) 属性升序排序，对询问我们进行离线处理，按 \(m\) 属性也是升序排序，这样就解决了这个问题了。
• 对于条件 \(b[i]>m+s\) ，组成属性 \(c\) 之和等于 \(k\) 的方案可能有多种我们维护这些方案中物品的最小的 \(b\) 属性，且尽量让它最大。这样如果当前能组成 \(k\) 的方案中最小的 \(b\) 属性最大的能满足条件，则所有条件均满足。
• 定义：\(f[i]\) ，表示满足 \(a\) 属性的 \(c\) 属性之和为 \(i\) 的方案中最小的 \(b\) 属性的最大值(好拗口，好好想)。

Code

#include <bits/stdc++.h>
const int maxn=1e3+5,maxv=1e5+5,Inf=0x3f3f3f3f;
struct Nodea{
    int a,b,c;
    bool operator <(const Nodea &A)const{
        return a<A.a;
    }
}a[maxn];
struct Nodeb{
    int m,k,s,id;
    bool operator <(const Nodeb &b)const{
        return m<b.m;
    }
}b[10*maxv];
int n,m;
int f[maxv],ans[10*maxv];//f[i]表示所选满足条件物品c属性和为i，所选物品的最小的b属性值
void Init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d%d",&a[i].c,&a[i].a,&a[i].b);
    scanf("%d",&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&b[i].m,&b[i].k,&b[i].s);
        b[i].id=i;
    }
    std::sort(a+1,a+n+1);
    std::sort(b+1,b+m+1);
}
void Solve(){
    f[0]=Inf;
    int j=1;
    for(int i=1;i<=m;++i){//枚举每个询问
        while(j<=n && a[j].a<=b[i].m){//枚举每个满足条件的询问
            for(int k=100000;k>=a[j].c;--k)//类似背包容积
                f[k]=std::max(f[k],std::min(f[k-a[j].c],a[j].b));
            ++j;
        }
        if(f[b[i].k]>b[i].m+b[i].s)//c属性之和的最大的b属性满足
            ans[b[i].id]=1;

    }
    
    for(int i=1;i<=m;++i){        
        if(ans[i])printf("TAK\n");
        else printf("NIE\n");
    }
}
int main(){
    Init();
    Solve();
    return 0;
}

Cloakroom

原文：https://www.cnblogs.com/hbhszxyb/p/13334995.html