2020蓝桥杯国赛B组-搬砖-(贪心排序+01背包)

J

题意：
就是给你n个砖头，每个砖头有个重量和价值，现在让你把一些砖块垒起来，对于每个砖块，他上面的所有砖块的重量不能超过他本身的价值。问你这个垒起来的砖块价值总和最大是多少。

思考：
比赛时感觉后面的也都不简单，实际上多思考思考就好了。首先想到的就是dp，但是对于每个砖块怎么保证，他上面的重量总和小于等于他的价值呢，这个该怎么维护呢。实际上在纸上画一画，思考一下可以先处理上面的砖块，再处理下面的砖块，一点一点的处理，因为你如果先处理下面的砖块，你怎么选对吧，才能保证下面的都满足。所以先考虑上面的，从上往下每个砖块都能线性处理。定义dp[i][j]是用了前i个砖块，此时重量为j的时候的最大价值。但是这样该怎么枚举砖块的顺序呢？实际上这就是要排序，以前就做过这种，比如国王的游戏。这题可以让i在上面，j在下面，我们让wi+sum<vj，wj+sum>vi，也就是让i在上面的时候j可以选，让i在下面的时候，j不可以选了。所以转化一下这个公式，可以把sum丢掉，sum是上面所有的重量。然后公式就是wi<vj,vi<wj。两个想加可以得到wi+vi<wj+vj。所以按这个排序就行。然后对于维护每个砖块上面的重量小于他的价值，其实在dp的时候加个判断条件就够了。然后其实就是01背包，加了一个贪心排序，和多了一个判断条件。可以优化为1维的。

二维版本：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 1e5+10,M = 2010;

int T,n,m,k;
PII va[N];
int dp[1005][20005];

bool cmp(PII A,PII B)
{
	return A.fi+A.se<B.fi+B.se;
}

signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
	sort(va+1,va+1+n,cmp);
	m = n*20; //重量最多是这些
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			dp[i][j] = max(dp[i][j],dp[i-1][j]); //如果这个砖块不选
			if(va[i].se>=j-va[i].fi&&j>=va[i].fi) dp[i][j] = max(dp[i][j],dp[i-1][j-va[i].fi]+va[i].se); //如果选，要保证价值大于上面的总重量。
		}
	}
	int maxn = 0;
	for(int j=0;j<=m;j++) maxn = max(maxn,dp[n][j]);
	cout<<maxn;
	return 0;
}

一维版本：
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 1e5+10,M = 2010;

int T,n,m,k;
PII va[N];
int dp[20005];

bool cmp(PII A,PII B)
{
	return A.fi+A.se<B.fi+B.se;
}

signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
	sort(va+1,va+1+n,cmp);
	m = n*20;
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=0;j--)
		{
			if(va[i].se>=j-va[i].fi&&j>=va[i].fi)
			dp[j] = max(dp[j],dp[j-va[i].fi]+va[i].se);
		}
	}
	int maxn = 0;
	for(int j=0;j<=m;j++) maxn = max(maxn,dp[j]);
	cout<<maxn;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

总结：
多多思考呀，其实都不难，这就是以前在upc做过的原题可以说。