感觉也许是题解太老的缘故，什么和 $0$ 取 $\max$ 与其 DP 真实的含义矛盾，不然就是搞复杂了 DP，在这里我将讲解最正常的 DP。

DP 状态

$dp_{i,j}$：前 $i$ 个物品，恰好剩余 $j$ 个钩子的最小代价。

这里有个性质：

如果剩余的钩子 $\ge n$ 那么后面随便选不用 DP，直接后缀和记入答案即可。

依照这个性质我们 DP 的第二维可以只开 $O(n)$，所以这题可做，但是实际上我们在第一次 $\ge n$ 的时候最大会达到 $2n$，但都是些小问题。

初始化

由于是“恰好”所以我们初始化必须除了 $f_{0,1}$ 全部设为 $-inf$ 来表示不合法。

转移式子

$f_{i,j}=\max(f_{i,j},f_{i-1,j-a+1}+b)$
其中 $j-a+1\ge 1$

排序的意义

我们想让第二维状态不为负数，所以才排序，如果你写个负下标 DP 就不用排序。

为什么很多人这个思路 WA 了？

因为你没有及时取 $\max$，导致后面能挂的钩子数量超出 $2n$ 大小，你就 DP 不到了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int QAQ=2100,inf=1e17;
int n,f[QAQ][QAQ*2],hz[QAQ];
struct xxx {int a,b;} d[QAQ];
bool cmp(xxx a,xxx b) {return a.a>b.a;}
signed main()
{
	cin>>n;
	for(int j=0;j<=n*2;j++) f[0][j]=-inf;
	f[0][1]=0;
	for(int i=1;i<=n;i++) cin>>d[i].a>>d[i].b;
	sort(d+1,d+n+1,cmp);
	for(int i=n;i;i--)
	{
		hz[i]=hz[i+1];
		if(d[i].b>0) hz[i]+=d[i].b;
	}
	int ans=0;
	for(int i=1,a,b;i<=n;i++)
	{
		a=d[i].a,b=d[i].b;
		for(int j=0;j<=n*2;j++)
		{
			f[i][j]=f[i-1][j];
			if(1<=j-a+1&&j-a+1<=2*n&&f[i-1][j-a+1]!=-inf) f[i][j]=max(f[i][j],f[i-1][j-a+1]+b);
			if(j>=n&&f[i][j]!=-inf) ans=max(ans,f[i][j]+hz[i+1]);
		}
	}
	for(int j=0;j<=n;j++) ans=max(ans,f[n][j]);
	cout<<ans;
	return 0;
}

思路

又是注意到的一天

注意到$n\leq2000$,考虑DP.

1.每一个挂饰具体挂在哪一个挂饰上这并不重要,毕竟每一个挂钩都是一样的,你只需要考虑目前还剩下几个挂钩.

2.考虑贪一手.更多的挂钩意味着更多的机会,所以首先按照挂钩数量排序.

3.发现一个问题:每一个挂饰挂钩数最大到$n-1$,$n$个挂钩就是$n\times (n-1)$再加上枚举每一个挂饰的$n$,炸的没边了.注意到 (第二次了) 如果你有超过$n$个挂饰,你具体有多少个都不重要了,毕竟就算剩下每一个挂饰都没有挂钩都够用,所以又狠狠的贪了一手时间.

4.设计一下状态.因为$n\leq2000$,完全够开$O(N^2)$,设计$f_{i,j}$表示前$i$个挂饰用完后剩下$j$个挂钩,转移方程大概长这样:

(其中$nj$表示挂完后会有多少个挂钩(贪过的),$j$表示原本有多少个挂钩)

5.注意到 (怎么又是它) $f[i][j]$只与$f[i-1][k]$有关,考虑开滚动数组贪一手空间.把原先的数组$f[N][N]$稍微修改为$f[2][N]$即可

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2010;
struct node{int a,b;}c[N];
int f[2][N],n;
bool cmp(node x,node y){return x.a>y.a;}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&c[i].a,&c[i].b);
	sort(c+1,c+n+1,cmp);
	memset(f,0xc0,sizeof(f));
	f[0][1]=0;
	for(int i=1;i<=n;i++)
	{
		int cur=i&1, pre=cur^1;
		for(int j=0;j<=n;j++) f[cur][j]=f[pre][j];
		int delta=c[i].a-1;
		for(int j=1;j<=n;j++)
		{
			if(f[pre][j]<=-1e18) continue;
			int nj=j+delta;
			if(nj>n) nj=n;
			if(nj>=0) f[cur][nj]=max(f[cur][nj],f[pre][j]+c[i].b);
		}
	}
	int ans=0;
	for(int j=0;j<=n;j++) ans=max(ans,f[n&1][j]);
	printf("%lld\n",ans);
	return 0;
}

感谢QWEN的帮助,顺便吐槽一下:这题咋有117个点?