J

Title:
It is to give you n bricks, each brick has a weight and value, and now let you build some bricks, for each brick, the weight of all the bricks above him cannot exceed its own value. Ask you what is the maximum total value of the bricks built up.

think:
During the game, I feel the latter part is not easy, but in fact, it is good to think more. The first thing that comes to mind is dp, but how to ensure that the sum of the weight on each brick is less than or equal to its value, and how to maintain this. In fact, draw a picture on the paper and think about how to deal with the upper bricks first, and then deal with the lower bricks, little by little, because if you deal with the lower bricks first, how do you choose the right one? Make sure the following are satisfied. So consider the above first, each brick can be processed linearly from top to bottom. Definition dp[i][j] is the maximum value when the first I bricks are used and the weight is J. But then how to enumerate the order of bricks? In fact, this is to sort, which has been done before, such as the game of kings. This question allows I to be on top and j to be on the bottom. We let wi+sum<vj, wj+sum>vi, that is, let I be on top and j be off below. So by transforming this formula, you can throw away the sum, which is all the weight above. Then the formula is wi<vj, vi<wj. Two would add to get wi+vi<wj+vj. So just sort by that. Then, to maintain the weight on each brick is less than its value, it is enough to add a judgment condition when DP is used. Then it is actually the 01 backpack, with a greedy sorting and an additional judgment condition. Can be optimized to be 1-dimensional.

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 most weight is these
	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 selected, 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;
}

1D 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;
}

Summarize:
Think about it a lot, it's actually not difficult, this is the original question that I have done in upc before.