记录编号	422947	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Nescafé 26] 小猫爬山	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	5.886 s
提交时间	2017-07-10 19:36:12	内存使用	2.29 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=18;
int n,W,sum[1<<N],dp[1<<N];
//dp[S]表示取了S中元素之后最少分组数
int main()
{
	freopen("koneko.in","r",stdin);
	freopen("koneko.out","w",stdout);
	scanf("%d%d",&n,&W);
	for (int i=0;i<n;i++){
		int c;
		scanf("%d",&c);
		sum[1<<i]=c;
	}
	for (int i=0;i<n;i++)
	for (int S=0;S<(1<<n);S++)
	if (S>>i&1) sum[S]+=sum[S^(1<<i)];
	for (int S=1;S<(1<<n);S++){//求dp[S]
		dp[S]=1e9;
		if (sum[S]<=W){dp[S]=1;continue;}
		for (int T=(S-1)&S;T;T=(T-1)&S) dp[S]=min(dp[S],dp[T]+dp[S^T]);
	}
	printf("%d\n",dp[(1<<n)-1]);
	return 0;
}