题解 [ABC056D] No Need

wind_seeker · 2023-08-24 15:17:50 · 题解

对于题目，先考虑性质。

先是一个朴素的性质：我们作背包，对于一个数，如果有一个方案，满足插入这个数前 < k，插入之后 \ge k，那么这个数不是可有可无。

然后就可以推出一个性质，如果我们把它降序排序以后再插入 ,可有可无的数字变成了一段后缀，下面是证明。

如果 a_i 满足朴素的性质，假设用前 i-1 个数拼成了 num 使得 num<k 并且 a_i+num\ge k，那么考虑 j<i：

• 如果 a_j 被用来凑成 num：满足 num+a_i-a_j< k\le num+a_i。
• 如果 a_j 不被用来凑成 num：显然 a_j+num\ge k，此时它也不是可有可无。

然后我们可以证明最后一个不是可有可无的数字 a_i 一定可以用它之前的数拼成 num。假设我们拼成了 num 满足 num<k\le num+a_i（注意这个 num 可以使用除了 a_i 剩下的所有数），那么找到一个 a_j 满足 j>i 并且被用来凑成 num：

• 如果 num+a_i-a_j\ge k，那么我们可以在 num 中删去 a_j。
• 否则 num'=num+a_i-a_j，那么 num'<k\le num'+a_j，a_j 并不是可有可无，与 i 是最后一个不是可有可无矛盾。

所以只要从前往后往背包里加数即可。

时间复杂度：\mathcal O(nk)。使用 bitset 可以优化到 \mathcal O(nk/w)。

#include<bits/stdc++.h>
using namespace std;
const int N=5010;

int n,k,a[N],dp[N],ans,al;

int read(){
    int res=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) res=(res<<3)+(res<<1)+(c^48);
    return res*f;
}

bool cmp(int x,int y){return x>y;}

int main(){
    haha,wozhendeshijuedingcongming,xinhaibukuishiwolaopo
    n=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1,cmp);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        if(a[i]>=k) {ans=i;continue;}
        for(int j=k-1;j>=0;j--){
            if(dp[j]&&j+a[i]>=k) ans=i;
            else if(dp[j]) dp[j+a[i]]=1;
        }
    }
    printf("%d\n",n-ans);
    return 0;
}