贪心、动态规划

缺少转化问题的意识。

由于 $n,W$ 同阶，直接枚举第 $i$ 种物品拿几个再跑完全背包的时间复杂度为 $O(n^3)$，不可接受。

第 $i$ 种物品拿 $k_i$ 个的价值是 $k_i (v_i - k_i)$，不等于拿 $k - x$ 个第 $i$ 种物品和拿 $x$ 个物品得到的价值之和，无法应用二进制优化。

进行转化，把第 $i$ 种物品拿 $k_i$ 个得到的价值改为拿 $k_i$ 个的价值与拿 $k_i - 1$ 个价值的差，因为物品单价 $v_i - k_i$ 随着 $k_i$ 的增长递减，若某一情况的最优方案中包含 $k_i$ 个第 $i$ 种物品的贡献则其必定包含 $k_i - 1$ 个第 $i$ 种物品的贡献。完成转化后物品总数还是 $O(n^2)$ 等级，继续优化。

发现重量为 $X$ 的物品至多被选择 $\left\lfloor \dfrac{W}{X} \right\rfloor$ 个，只更新前 $\left\lfloor \dfrac{W}{X} \right\rfloor$ 个重量为 $X$ 的物品可以把物品数量降低到 $O(\sum\limits_{i=1}^{n} \dfrac{n}{i}) = O(n \log n)$ 等级。

时间复杂度 $O(n^2 \log n)$。

#include<bits/stdc++.h>
using namespace std;
vector<int> v[3'005];
long long dp[3'005];
int n,m;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        static int x,y,lim;
        cin>>x>>y,lim=m/x;
        for(int j=1;j<=lim;j++){
            int w=1ll*j*(y-j)-1ll*(j-1)*(y-(j-1));
            v[x].push_back(w);
        }
    }
    for(int i=1;i<=m;i++){
        sort(v[i].begin(),v[i].end(),greater<int>());
        v[i].resize(m/i);
    }
    for(int i=1;i<=m;i++) for(int j:v[i])
        for(int k=m;k>=i;k--) dp[k]=max(dp[k],dp[k-i]+j);
    cout<<dp[m]<<'\n';
    return 0;
}