记录编号	474471	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Nescafé 26] 小猫爬山	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	5.888 s
提交时间	2017-11-10 08:03:58	内存使用	1.60 MiB

#include <cstdio>
#include <cstring>

const int M=1<<18;
int n,w;
int val[21],bit[21],wei[M],f[M];
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

inline void minn(int &x,int y) {if(x>y) x=y;}

int main(){
	freopen("koneko.in","r",stdin);
	freopen("koneko.out","w",stdout);
	n=read();w=read();bit[1]=1;
	memset(f,0x3f,sizeof(f));f[0]=0;
	for(int i=1;i<=n;++i) val[i]=read();
	for(int i=2;i<=20;++i) bit[i]=bit[i-1]<<1;
	for(int i=1;i<bit[n+1];++i){
		for(int j=1;j<=n;++j){
			if(i&bit[j]){
				wei[i]=wei[i^bit[j]]+val[j];
				if(wei[i]<=w) f[i]=1;
				break;
			}
		}
	}for(int i=1;i<bit[n+1];++i){
		if(wei[i]<=w) continue;
		for(int j=i;j;j=(j-1)&i)
			minn(f[i],f[j]+f[i^j]);
	}
	printf("%d",f[bit[n+1]-1]);
	return 0;
}
/*
18 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
*/