[bzoj1606][Usaco2008 Dec]Hay For Sale 购买干草_动态规划

Hay For Sale 购买干草 bzoj-1606 Usaco-2008 Dec

题目大意：约翰遭受了重大的损失：蟑螂吃掉了他所有的干草，留下一群饥饿的牛．他乘着容量为C(1≤C≤50000)个单位的马车，去顿因家买一些干草．顿因有H(1≤H≤5000)包干草，每一包都有它的体积Vi(l≤Vi≤C).约翰只能整包购买，他最多可以运回多少体积的干草呢？

想法：傻逼背包裸题，直接01背包即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 5010

#define M 50010

int a[N];

bool b[M];

int main()

{

	int m,n; cin >> m >> n ;

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	b[0]=true;

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

	{

		for(int j=m;j>=a[i];j--)

		{

			if(b[j-a[i]]) b[j]=true;

		}

	}

	for(int i=m;i>=0;i--) if(b[i]) { printf("%d\n",i); return 0; }

	// return 0;

}

/*

7 3

2

6

5

*/

小结：刷水... ...

巴特西

[bzoj1606][Usaco2008 Dec]Hay For Sale 购买干草_动态规划_背包dp

最新文章

热门文章