首先这道题没有规定选几个。
一开始我以为是全选，然后想了个贪心才发现看错了。
那我们先来假设选 \(m\) 个。
这个题的每个物品都会影响后面物品的收益，不好看。
由于每个物品 \(i\) 对后选的其他物品减少的收益都是 \(R_i\)，因此我们在保证总价值不变的情况下转化一下，把该物品的价值改为本身的收益和减少后面物品的收益的差。
设物品 \(i\) 是第 \(t_i\) 次被选到，则该物品的价值为 \(W_i-(m-t_i)R_i\)。
好像还不是很好看，因为我们不知道这个 \(m\) 应该多大。
有的时候要用逆向思维思考，所以我们不妨反过来想。
我们可以先考虑最后一个，再考虑倒数第二个，然后向前推进，这样我们重新设一下 \(t_i\) 为我们倒着考虑的顺序，那么该物品的价值为 \(W_i-t_iR_i\)。
这样就非常的清爽，因为我们不需要考虑 \(m\)，可以直接从 \(1\) 个数推到 \(n\) 个数的情况。
每个数只能选一次，然后求选 \(m\) 数的最优值，价值不一不好贪心，由此可以想到 01 背包。
但是直接跑 01 背包还是错的。附一份全 WA 代码。
constexpr int MAXN=3e3+10;
int n,dp[MAXN];
struct item{
int w,r;
}t[MAXN];
int main(){
n=read<int>();
for(int i=1;i<=n;++i){
t[i].w=read<int>();t[i].r=read<int>();
}
for(int i=1;i<=n;++i){
for(int j=i;j>=1;--j){
dp[j]=max(dp[j],dp[j-1]+t[i].w-(j-1)*t[i].r);
}
}
int ans=0;
for(int i=1;i<=n;++i)ans=max(ans,dp[i]);
printf("%d\n",ans);
return 0;
}
这样的 01 背包并不能覆盖到所有情况，至少是可能为最优解的情况。
很容易发现其中的 \(dp_n\) 只有从 \(1\) 选到 \(n\) 的情况。
然而跑 \(n\) 遍这个过程不仅会超时，而且会把这个问题写成一个完全背包。
好像没什么思路，我们再来研究题目的性质。
容易发现，在选择的物品固定的情况下，该选择的方案的好坏只与选择顺序和他们对其他物品影响的 \(R_i\) 有关，我们在贪心思想的基础上可以先选 \(R_i\) 小的物品 \(i\)。
在选择的物品固定的情况下，我们会得到一种选择的顺序，会排除掉一些不优的情况。
我们通过比较 \(R_i\) 对物品进行排序，得到了物品选择的顺序，在这个基础上跑 01 背包解决选哪些数的问题，即可得到最优解。
一个细节就是由于我们是倒着考虑的，所以应该把 \(R_i\) 大的物品放在前面。
代码如下。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int MAXN=3e3+10;
int n,dp[MAXN];
struct item{
int w,r;
}t[MAXN];
template<typename T>
T read(){
T f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return f*x;
}
namespace sol{
bool cmp(item x,item y){
return x.r>y.r;
}
void solve(){
n=read<int>();
for(int i=1;i<=n;++i){
t[i].w=read<int>();t[i].r=read<int>();
}
sort(t+1,t+n+1,cmp);
for(int i=1;i<=n;++i){
for(int j=i;j>=1;--j){
dp[j]=max(dp[j],dp[j-1]+t[i].w-(j-1)*t[i].r);
}
}
int ans=0;
for(int i=1;i<=n;++i)ans=max(ans,dp[i]);
printf("%d\n",ans);
}
}
int main(){
sol::solve();
return 0;
}