2018.08.10 atcoder No Need(线性dp)
传送门
输入一个序列an" role="presentation" style="position: relative;">anan,输入k" role="presentation" style="position: relative;">kk。
如果对于所有包含ai" role="presentation" style="position: relative;">aiai,且和大于等于k" role="presentation" style="position: relative;">kk的集合,去掉ai" role="presentation" style="position: relative;">aiai之后和还大于等于k" role="presentation" style="position: relative;">kk,那么ai" role="presentation" style="position: relative;">aiai就是可有可无的。
求出可有可无的元素的个数。
可有可无的元素一定是最小的若干个,于是在排序之后看看如果有i" role="presentation" style="position: relative;">ii满足a[i],a[i+1],...,a[n]" role="presentation" style="position: relative;">a[i],a[i+1],...,a[n]a[i],a[i+1],...,a[n]这些数凑不出[max(k−sum,0),k−1]" role="presentation" style="position: relative;">[max(k−sum,0),k−1][max(k−sum,0),k−1]中的任何数,说明1" role="presentation" style="position: relative;">11~i−1" role="presentation" style="position: relative;">i−1i−1这些数都是可有可无的。
代码:
#include<bits/stdc++.h>
using 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;
}
最新文章
- C语言 &#183; 未名湖边的烦恼
- C语言文件方式输入与输出(最简洁方便实用的一种方式)
- 【转载】关于Alipay支付宝接口(Java版)
- javascript宿主对象之window.location
- 【规范】javascript 变量命名规则(转)
- C#中的try catch finally
- UVA 10106 (13.08.02)
- linux下ssh使用和配置
- 什么是券商PB业务
- yii 删除内容时增加ajax提示
- GridView的RowCreated与RowDataBound事件区别
- ASP.NET Web基本原理
- Mysql中autocommit的用法
- lua-nginx-module模块里ngx_lua的所有指令以及可用ngx所有方法
- HDU 6152 - Friend-Graph
- zip4j压缩
- JavaScript 基础六 &#39;use strict&#39;严格模式下的规则
- 【Linux】scp指令
- wordpress练习
- 如何用iptables实现NAT(转)