link:http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=4766

唉。。这这这。。。已经不能用无语来形容了,又一次被人家完虐啊、、、不过也好,
让自己知道了好多地方还不懂,下面的时间要开始看看新的内容了,不求所有都吃透
,但好得让我知道有这个东西,那么做题的时候也好有个选择。。。
讲讲这题吧,前几天偶尔瞟了几眼dp和背包,看到这题的第一印象就是0-1背包,
然后就下手做了。。。代码写完了,发现坑爹的那m竟然那么大,
我的程序肯定爆nei存...后来又写了个dp,准备碰运气看看怎么样的,
结果无语的是竟然连cb都运行不了,开的二维数组必超啊、、、唉、、、
然后看到群里面大牛在讨论这题,有人说用爆搜做的,我也试了一下,16:59:26险过、、、
算是碰到了、、加上几剪枝,防止超时、、、
下面是我的代码
code:

 

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int a[31],n,m,j;
int max1;
void dfs(int s,int sum)
{
	if(max1==m)
		return;
	if(s==j)
	{
		max1=max1>sum?max1:sum;
		return;
	}
	if(sum+a[s]<=m)
	{
		dfs(s+1,sum);
		dfs(s+1,sum+a[s]);
	}
	if(sum>=max1)
	{
		max1=sum;
		return;
	}
}
int main()
{
	int i,sum,x,flag;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		sum=0,flag=0;
		for(i=0,j=0;i<n;i++)
		{
			scanf("%d",&x);
			if(x<m)
			{
				a[j++]=x;
				sum+=x;
			}
			if(x==m)
				flag=1;
		}
		if(flag)
		{
			printf("%d\n",m);
			continue;
		}
		if(m==0)
		{
			printf("%d\n",0);
			continue;
		}
		if(sum<=m)
		{
			printf("%d\n",sum);
			continue;
		}
		sort(a,a+j);
		max1=-1;
		dfs(0,0);
		printf("%d\n",max1);
	}
	return 0;
}
菜鸟之作,仅供参考,如有错误,请您指出——Tamara

发表评论

电子邮件地址不会被公开。

Post Navigation