ABC 373 F - Knapsack with Diminishing Values

原题链接：F

题意：给n个物品，每个物品有二种属性，第一种为重量，第二种为价值，每个物品有无限个，最多拿总重不多于W的物品，每种物品提供的幸福值是价值*拿的数量-拿的数量*拿的数量。

思路：一道很神奇的dp题。令g[i][j]为拿重量为i的物品，拿j个的时候的幸福度，f[i][j]为拿重量小于i的物品，总重小于j的情况下的幸福度。观察可以知道，幸福度的方程是二次函数，如果多拿一个物品，那么就会多价值-2-1的幸福度，那么就可以先求出g数组的值，然后求f数组就可以得到答案。

//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
#define count2(x) __builtin_popcountll(x)
#define is2(x) __builtin_ffsll(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
ll g[3010][3010],f[3010][3010];
vector<ll> mp[N];
void Jiuyuan()
{ll n,xz;cin>>n>>xz;for(int i=1;i<=n;i++){ll a,b;cin>>a>>b;mp[a].push_back(b);}for(int i=1;i<=xz;i++){priority_queue<ll> kp;for(auto v:mp[i])kp.push(v-1);for(int j=1;kp.size()&&xz>=i*j;j++){ll v=kp.top();kp.pop();g[i][j]=g[i][j-1]+v;v-=2;if(v>=0)kp.push(v); }}for(int i=1;i<=xz;i++){for(int j=1;j<=xz;j++){for(int k=0;j>=i*k;k++){f[i][j]=max(f[i][j],f[i-1][j-i*k]+g[i][k]);}}}cout<<f[xz][xz];
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;
//	cin>>T;while(T--){Jiuyuan();}return 0;
}