输入一个序列anan,输入kk。 如果对于所有包含aiai,且和大于等于kk的集合,去掉aiai之后和还大于等于kk,那么aiai就是可有可无的。 求出可有可无的元素的个数。
可有可无的元素一定是最小的若干个,于是在排序之后看看如果有ii满足a[i],a[i+1],...,a[n]a[i],a[i+1],...,a[n]这些数凑不出[max(k−sum,0),k−1][max(k−sum,0),k−1]中的任何数,说明11~i−1i−1这些数都是可有可无的。
代码:#includeusing namespace std;int f[5050],a[5050],n,k,sum=0;int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;++i)scanf("%d",&a[i]),a[i]=min(a[i],k),sum+=a[i]; sort(a+1,a+n+2),f[0]=1; for(int i=n+1;i;--i){ bool check=true; for(int j=k-1;j>=k-sum&&j>=0;--j)if(f[j]){check=false;break;} if(check){ printf("%d",i-1);return 0;} for(int j=k;j>=a[i];--j)f[j]|=f[j-a[i]]; sum-=a[i]; } return 0;}