挂饰

wjh15101051's space

卧薪尝胆，厚积薄发。

挂饰

Date: Sun Sep 09 16:11:41 CST 2018

In Category: NoCategory

Description：

有 $n$ 个挂件，每个挂件都有一些挂钩，还有一个挂钩用来挂在别的挂钩上，最开始有一个挂钩，每个挂钩有价值，最大化最终价值。

$1\le n \le 2000$

Solution：

先按挂钩数排序，防止被建成负的但最终合法的情况出现，然后背包，如果超过 $n$ 那么所有的都能挂上，所以用一些技巧处理。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 2010

int f[MAXN][MAXN << 1];

int n;

#define INF 0x3f3f3f3f

int ans = -INF;

struct pack{int v,c;}s[MAXN];

bool cmp(pack x,pack y){return x.v > y.v;}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d%d",&s[i].v,&s[i].c);

	sort(s + 1,s + 1 + n,cmp);

	memset(f,0xc0,sizeof(f));

	f[0][1] = 0;

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

	{

		for(int j = 0;j <= n;++j)

		{

			f[i][j] = max(f[i - 1][max(j - s[i].v,0) + 1] + s[i].c,f[i - 1][j]);

		}

	}

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

	{

		ans = max(ans,f[n][i]);

	}

	cout << ans << endl;

	return 0;

}

In tag: DP-背包

wjh15101051