它是个背包 我们就做背包 因为体积范围很小 我们按体积分类 然后因为当我们决策某个体积拿多少个时肯定拿价值大的前几个 我们按体积划分阶段DP 然后发现转移都是在差为体积整数倍之间 按照容量对体积取模分组 发现组内部转移满足神奇的决策单调性？！ 然后就大力分治一发 O(KClogC)
正解肯定不是这个 正解肯定不是这个 正解肯定不是这个 正解真的不是这个 应该 O(KC)
#include<cstdio> #include<cstdlib> #include<algorithm> #include<functional> #include<vector> using namespace std; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } int n,m,maxc; vector<ll> a[305]; ll f[2][100005]; ll lst[50005],pnt; int x,b,t; inline void Solve(int l,int r,int al,int ar){ if (l>r) return; int i=(l+r)>>1,d=i; f[t^1][i*x+b]=f[t][i*x+b]; for (int j=min(ar,i-1);j>=al;j--){ if (i-j>(int)a[x].size()) break; if (f[t][j*x+b]+a[x][i-j-1]>f[t^1][i*x+b]) f[t^1][i*x+b]=f[t][j*x+b]+a[x][i-j-1],d=j; } Solve(l,i-1,al,d); Solve(i+1,r,d,ar); } int main(){ int _x,_y; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(n); read(m); for (int i=1;i<=n;i++) read(_x),read(_y),a[_x].push_back(_y),maxc=max(maxc,_x); for (int i=1;i<=maxc;i++) { sort(a[i].begin(),a[i].end(),greater<int>()); for (int j=1;j<(int)a[i].size();j++) a[i][j]+=a[i][j-1]; } t=0; for (x=1;x<=maxc;x++){ if (a[x].size()==0) continue; for (b=0;b<x;b++){ Solve(0,(m-b)/x,0,(m-b)/x); } for (int j=1;j<=m;j++) f[t^1][j]=max(f[t^1][j],f[t^1][j-1]); t^=1; } for (int i=1;i<=m;i++) printf("%I64d%c",f[t][i],i==m?'\n':' '); return 0; }