题解：P16160 [ICPC 2016 NAIPC] Jewel Thief
int4399
·
·
题解
发现唯一的性质是 s\le 300，那么我们先分组，显然我们会从权值从大往小选，那么再降序排序，记 a_{i,j} 表示大小为 i 的物品，前 j 个最贵的价值和为 a_{i,j}，然后做一个分组背包。设 f_{i,j} 表示前 i 轮背包装了重量为 j 的物品的最大价值，转移就是
我们去掉第一维，转移式变为 $f'_j=\max\limits_{0\le k\le j} f'_k+a_{i,j-k}$。令 $w(l,r)=a_{i,r-l}$，发现 $w(l,r)+w(l-1,r+1)-w(l-1,r)-w(l,r+1)=a_{i,r-l}+a_{i,r-l+2}-2a_{i,r-l+1}=b_{i,r-l+2}-b_{i,r-l+1}\le 0$，（其中 $b_{i,j}$ 表示第 $i$ 组第 $j$ 贵的价值是多少）所以 $w$ 满足四边形不等式，那么 $f'$ 有决策单调性，直接上分治做即可。复杂度是 $O(sk \log n+n\log n)$。
```
#include<bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
using namespace std;
const int S=305,V=1e5+5;
ll n,k,f[V],g[V],lst[V];
vector<ll> a[S];
ll w(int l,int r,int t){return a[t][r-l];}
void solve(int l,int r,int L,int R,int t){
if(l>r) return;
ll best=-1,o=0;
for(int i=L;i<=R&&i<=mid;i++)if(mid-i<a[t].size()&&lst[i]+w(i,mid,t)>best) best=lst[i]+w(i,mid,t),o=i;
g[mid]=best,solve(l,mid-1,L,o,t),solve(mid+1,r,o,R,t);
}int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1,s,v;i<=n;i++) cin>>s>>v,a[s].push_back(v);
for(int i=1;i<=300;i++){
sort(a[i].begin(),a[i].end(),[](ll x,ll y){return x>y;});a[i].insert(a[i].begin(),0);
for(int j=1;j<a[i].size();j++) a[i][j]+=a[i][j-1];
}for(int i=1;i<=300;i++)for(int id=0;id<i;id++){
int num=(k-id)/i;if(num<0) continue;
for(int j=0;j<=num;j++) lst[j]=f[j*i+id];
solve(0,num,0,num,i);
for(int j=0;j<=num;j++) f[j*i+id]=g[j];
}for(int i=1;i<=k;i++) f[i]=max(f[i-1],f[i]),cout<<f[i]<<' ';
return 0;
}
```