记录编号	45328	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Nescafé 26] 小猫爬山	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2012-10-23 13:55:43	内存使用	13.66 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
using namespace std;

int n,limit,mid,a[20],lift[20];
bool ok;

void dfs(int deep)
{
	int i;
	if (deep==n)
	{
		ok=true;
		return;
	}
	for (i=1;i<=mid;i++)
	{
		if (lift[i]+a[deep+1]<=limit)
		{
			lift[i]+=a[deep+1];
			dfs(deep+1);
			if (ok)
				return;
			lift[i]-=a[deep+1];
		}
	}
}

int main(void)
{
	freopen("koneko.in","r",stdin);
	freopen("koneko.out","w",stdout);
	int i,s=0,l,r;
	cin>>n>>limit;
	for (i=1;i<=n;i++)
	{
		cin>>a[i];
		s+=a[i];
	}
	if (s%limit)
		l=s/limit+1;
	else
		l=s/limit;
	r=n;
	mid=(l+r)>>1;
	while (l<r)
	{
		ok=false;
		memset(lift,0,sizeof(lift));
		dfs(0);
		if (ok)
			r=mid;
		else
			l=mid+1;
		mid=(l+r)>>1;
	}
	cout<<mid<<endl;
	return(0);
}