2020 Blue Bridge Cup group B - move bricks - (greedy sorting +01 backpack)

J

The question ：
It's for you. n A brick , Each brick has a weight and value , Now let's put some bricks together , For each brick , The weight of all the bricks on him cannot exceed his own value . Ask you what is the maximum total value of the bricks built up .

reflection ：
When the game was played, I felt that it was not easy , In fact, just think more . The first thing that comes to mind dp, But how to guarantee for each brick , The total weight on him is less than or equal to his value , How to maintain this . Actually draw a picture on paper , Think about how you can deal with the bricks first , Then dispose of the bricks below , Bit by bit , Because if you deal with the bricks below first , How do you choose , To ensure that the following are met . So first consider the above , Each brick from top to bottom can be processed linearly . Definition dp[i][j] Yes, before use i A brick , At this time, the weight is j The greatest value when . But how do you enumerate the order of bricks ？ In fact, this is to sort , I have done this before , Like the king's game . This question can make i on top ,j Hereunder , We let wi+sum<vj,wj+sum>vi, Also is to let i When it's up there j You can choose , Give Way i Down there ,j No choice . So convert this formula , You can put sum lose ,sum It's all the weight above . And the formula is wi<vj,vi<wj. If you want to add two, you can get wi+vi<wj+vj. So just sort by this . Then for maintenance, the weight on each brick is less than its value , Actually in dp It is enough to add a judgment condition when . And then it's actually 01 knapsack , Added a greedy sort , And one more judgment condition . It can be optimized to 1 Dimensional .

Code ：

 2D version ：

#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; // The weight is these at most 
	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 this brick is not selected 
			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); // If elected , Make sure the value is greater than the total weight above .
		}
	}
	int maxn = 0;
	for(int j=0;j<=m;j++) maxn = max(maxn,dp[n][j]);
	cout<<maxn;
	return 0;
}

 One dimensional version ：
#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;
}

summary ：
Think more , It's not hard , This is what I used to do in upc The original question I have done can be said .