\(01\) 背包的 trick。
Link.
做法 \(1\)
暴力背包。超时。
做法 \(2\)
一个显然的性质就是，按 \(c_i\) 归类，先用价值大的。
如果无法更新背包，直接退出循环即可。
亲测能获得 85pts 的好成绩。
时间复杂度同暴力背包。（理论）
做法 \(3\)
如果你认真打了表，会发现如果从大往小放，那么最后一个更新的点是在递增的。
这一个很好理解，更新点只会右移。
加上这个小优化，虽然理论复杂度和暴力没区别，但是就是能草过去。
点击查看代码
#include<bits/stdc++.h>
#define N 50005
#define M 305
#define ll long long
#define reg register
using namespace std;
int n,m;
ll f[N];
vector <int>E[M];
inline int read()
{int s=0;char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9'){s=(s<<3)+(s<<1)+c-'0';c=getchar();}return s;
}
int main()
{
// freopen("a1.in","r",stdin);n=read(),m=read();for(reg int i=1;i<=n;i++){int c,v;c=read(),v=read();E[c].push_back(v);}for(reg int i=1;i<=M-5;i++){if(E[i].empty()) continue;sort(E[i].begin(),E[i].end());int used=1,pos=i;for(reg int k=E[i].size()-1;k>=0;k--){int now=E[i][k];used=0;for(reg int j=m;j>=pos;j--)if(f[j]<f[j-i]+now) f[j]=f[j-i]+now,used=j;pos=used;if(!used) break;}}for(int i=1;i<=m;i++) printf("%lld ",f[i]);return 0;
}
做法 \(4\)
所以在同一纬度内有决策单调性。
我们定义 \(f_{i,j}\) 表示第 \(i\) 类物品花 \(j\) 元的最大价值。
所以转移方程是 \(f_{i,j}=\min f_{i-1,j-kc}+w(k)\)
按 \(k\) 分类转移即可。
时间复杂度 \(O(Cm\log m)\)。
#include<bits/stdc++.h>
#define N 50005
#define M 305
#define K 1000005
#define ll long long
#define reg register
using namespace std;
int n,m;
ll f[N],g[N];
vector <ll>E[M];
inline int read()
{int s=0;char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9'){s=(s<<3)+(s<<1)+c-'0';c=getchar();}return s;
}
ll sum[K];
void solve(int l,int r,int ql,int qr,int k,int cur)
{if(l>r||ql>qr) return;int mid=(l+r)/2*k+cur;ll maxx=-1;int pos=1145141919;for(int i=ql;i<=min(mid,qr);i+=k)if(g[i]+sum[(mid-i)/k]>maxx) maxx=g[i]+sum[(mid-i)/k],pos=i;f[mid]=maxx;mid=(l+r)/2;solve(l,mid-1,ql,pos,k,cur);solve(mid+1,r,pos,qr,k,cur);
}
int main()
{n=read(),m=read();for(reg int i=1;i<=n;i++){int c,v;c=read(),v=read();E[c].push_back(v);}for(reg int i=1;i<=M-5;i++){if(E[i].empty()) continue;sort(E[i].begin(),E[i].end());int len=E[i].size();memset(sum,0,sizeof sum);for(reg int k=1;k<=min(len,m);k++)sum[k]=sum[k-1]+1ll*E[i][len-k];for(int i=len+1;i<=m;i++) sum[i]=sum[i-1];memcpy(g,f,sizeof g);for(int k=0;k<i;k++){int R=(m/i)*i+k;if(R>m) R-=i;solve(0,(R-k)/i,k,R,i,k);}}for(int i=1;i<=m;i++) printf("%lld ",f[i]);return 0;
}
