bzoj 1673: [Usaco2005 Dec]Scales 天平【dfs】

真是神奇

根据斐波那契数列，这个a[i]<=c的最大的i<=45，所以直接搜索即可

#include<iostream>

#include<cstdio>

using namespace std;

const int N=1005;

int n;

long long a[N],b[N],tot,s[N],c,ans;

void dfs(int w,long long v)

{

	if(v+s[w-1]<=c)

	{

		ans=max(ans,v+s[w-1]);

		return;

	}

	ans=max(ans,v);

	for(int i=w-1;i;i--)

	{

		v+=b[i];

		if(v<=c)

			dfs(i,v);

		v-=b[i];

	}

}

int main()

{

	scanf("%d%lld",&n,&c);

	for(int i=1;i<=n;i++)

	{

		scanf("%lld",&a[i]);

		if(a[i]<=c)

			b[++tot]=a[i];

		s[i]=s[i-1]+b[i];

	}

	dfs(tot+1,0);

	printf("%lld\n",ans);

	return 0;

}

巴特西

bzoj 1673: [Usaco2005 Dec]Scales 天平【dfs】

最新文章

热门文章