对于状态 $dp_{i,j}$，当 $j < a_i$ 时，由于挂上第 $i$ 个挂件后空闲挂件 $j'$ 一定满足 $j'\geq a_i$，那么对于该状态不能选第 $i$ 个挂件，为什么我这样处理 WA on #5 #10，但当 $j < a_i$ 时把 $j-a_i$ 强行看作 $0$ 才能通过？

$80 \ pts$ 代码：

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
const int N=2015;
const long long INF=0x3f3f3f3f3f3f3f3fll;

inline void FileIO() {
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}

template<typename Type>
inline void read(Type& res) {
	Type x=0,f=1;
	char c=' ';
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	res=x*f;
}

#define x first
#define y second

pii a[N];
ll dp[N][N],n,ans;

signed main() {
//	不开longlong见祖宗！
//	检查数组大小！
//	禁止在int乘int时不开longlong！
//	注意输出格式！ 
//	STL数据类型拷贝赋值时间复杂度是 O(N)！
//	读入单个字符要用字符串，防毒瘤数据！
//	(1<<63)爆ll，(1<<31)爆int！
//	比赛结束前5min，检查上述7项，并编译运行！！！！！ 
//	-std=c++14 -O2 -Wall -Wextra -Wshadow
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i].x);
		read(a[i].y);
	}
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	memset(dp,-0x3f,sizeof(dp));
	dp[0][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=dp[i-1][j];
			if(j-a[i].x+1>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].x+1]+a[i].y);
			ans=max(ans,dp[i][j]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

更改后 AC 代码：

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
using namespace std;
const int N=2015;
const long long INF=0x3f3f3f3f3f3f3f3fll;

inline void FileIO() {
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}

template<typename Type>
inline void read(Type& res) {
	Type x=0,f=1;
	char c=' ';
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	res=x*f;
}

#define x first
#define y second

pii a[N];
ll dp[N][N],n,ans;

signed main() {
//	不开longlong见祖宗！
//	检查数组大小！
//	禁止在int乘int时不开longlong！
//	注意输出格式！ 
//	STL数据类型拷贝赋值时间复杂度是 O(N)！
//	读入单个字符要用字符串，防毒瘤数据！
//	(1<<63)爆ll，(1<<31)爆int！
//	比赛结束前5min，检查上述7项，并编译运行！！！！！ 
//	-std=c++14 -O2 -Wall -Wextra -Wshadow
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i].x);
		read(a[i].y);
	}
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	memset(dp,-0x7f,sizeof(dp));
	dp[0][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=dp[i-1][j];
			dp[i][j]=max(dp[i][j],dp[i-1][max(j-a[i].x+1,1)]+a[i].y);
			ans=max(ans,dp[i][j]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

只要对思路有帮助都会 2 关