身为两个死对头，这题很好地将贪心和 (dp) 结合了起来。
首先考虑一下买一个东西对之后所有东西的影响。不难发现，当我们所买的东西相同的时候，肯定是先买影响最小物品最划算。所以我们要 排序。
现在，我们就把问题转化为了：
如何买一堆物品，每个物品有一个价值，且价值取决于之后所购买的物品的数量，使得总价值最大。
不妨设 (dp_{i,j}) 表示在从后往前第 (i) 个物品这里，买了 (j) 个物品的最大收益。而如果我们倒着转移，会有些不方便（不习惯）。于是，把排序反一下，大的排在前面，然后设当前第 (i) 个物品为最早买的就好啦。
至于 (dp) 方程，考虑买与不买两种情况。
- 对于买的情况，我们的价值没有变。(dp_{i,j} = dp_{i-1,j})
- 对于不买的情况，考虑价值的变化量。 (dp_{i,j-1} = dp_{i-1,j-1} + w_i - p_i * j)。
- 边界：(dp_{1,1} = w_1)，即只买第一个物品。
综合起来取 (max) 就好啦！
#include <bits/stdc++.h>
using namespace std;
#define N 3010
#define ll long long
template <class T>
inline void read(T& a){
T x = 0, s = 1;
char c = getchar();
while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
a = x * s;
return ;
}
int dp[N][N];
int w[N], p[N];
int n;
int ans = 0;
struct node{
int w, p;
bool operator < (const node& a) const{
return p > a.p;
}
} a[N];
int main(){
read(n);
for(int i = 1; i <= n; i++)
read(a[i].w), read(a[i].p);
sort(a + 1, a + n + 1);
dp[1][1] = a[1].w;
for(int i = 2; i <= n; i++){
for(int j = 0; j <= i; j++){
if(j) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + a[i].w- a[i].p * (j - 1)); // 买第 i 个
dp[i][j] = max(dp[i][j], dp[i-1][j]);
}
}
for(int i = 1; i <= n; i++)
ans = max(ans, dp[n][i]);
cout << ans << endl;
return 0;
}