AT2346 [ARC070B] No Need

学了两种思路

一种直接背包

参考自https://blog.csdn.net/ShadyPi/article/details/81738705

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define maxn 5005
using namespace std;
ll dp[maxn];
ll a[maxn];
int n;
ll k;
ll sum;

int main()
{
    scanf("%d%lld",&n,&k);
    sum=0;
    for(int i=1;i<=n;i++)
        {scanf("%lld",&a[i]);
        a[i]=min(a[i],k);
        sum+=a[i];
        }
        sort(a+1,a+n+1);
        dp[0]=1;

        for(int i=n,flag=0;i>=0;sum-=a[i--],flag=0)
        {

                for(int j=k-1;j>=k-sum&&j>=0;j--)
                    if(dp[j])
                    flag=1;

            if(!flag)
            {
                printf("%d\n",i);
                return 0;
            }
            for(int j=k;j>=a[i];j--)
                dp[j]|=dp[j-a[i]];

       

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<cstring>
#define  maxn 5500
using namespace std;
bitset<maxn>sum;
int a[maxn];
int n,k;
bool check(int x)
{
    if(a[x]>=k)
        return 1;
    sum.reset();
    sum[0]=1;
    for(int i=1;i<=n;i++)
        if(i!=x)
        sum|=sum<<a[i];
    for(int i=k-1;i>=k-a[x];i--)
        if(sum[i])
        return 1;
    return 0;
}

int main()
{scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
sort(a+1,a+n+1);
    int l=0;
    int r=n+1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }
    printf("%d\n",l-1);
    return 0;
}

AT2346 [ARC070B] No Need

原文：https://www.cnblogs.com/yaba/p/13850246.html