LINK：珠宝
去年在某个oj上写过这道题 当时懵懂无知wa的不省人事 终于发现这个东西原来是有决策单调性的。
可以发现是一个01背包 但是过不了 冷静分析 01背包的复杂度有下界 如果过不了说明必然存在某种特殊的条件。
果然 物品的代价<=300. 一个贪心对于代价相同的物品显然可以优先选取最大的 我们把代价相同的物品给压在一起。
可以发现 这类似于分组背包的dp f[i]表示i容量的最大值 f[i]=max(f[i-j*c]+w[c][j]);
不过这个w数组差分之后是逐渐递减的。
可以发现 可以利用单调队列优化 不过我们只能维护一半单调队列 因为队列里的点的值每次增加各不相同 也并不单调。
所以无法快速查找决策。
但是 我们可以考虑一下决策的单调性 对于 i来说 有决策 i-kp 或者 i-wp (w>k). 如果前者比后者优那么对于更大的 i来说 刚刚的i-kp仍然比i-wp优 因为w数组是差分后单调递减的 所以显然。
所以对于一个点w来说 其最优决策为 k 那么对于比w大的那些点来说 决策是单调递增的。
对于决策单调性优化dp 可以采用分治法 或者 存三元组单调队列上二分法。
这里建议采用分治法 简单粗暴 好写 常数小。
一个小坑点：在分治的时候 >=也要更新 因为可能之后的所有决策没有能更新当前mid的 也没有能和mid相等的 这个点可能更新后面的点 所以我们要保留这样的一个点来对后面造成贡献。
可以发现对前面没有什么影响。
const int MAXN=1000010;
int n,m,maxx,now;
vector<ll>v[310];
ll f[MAXN],g[MAXN],s[MAXN],sum[MAXN];
inline ll cmp(ll x,ll y){return x>y;}
inline void solve(int l,int r,int L,int R)//L~R为决策转移空间
{
int mid=(l+r)>>1;
int p=mid;g[mid]=s[mid];
for(int i=L;i<=R&&i<mid;++i)
{
ll ww=s[i]+sum[mid-i];
if(ww>g[mid])g[mid]=ww,p=i;
}
if(l<mid)solve(l,mid-1,L,p);
if(r>mid)solve(mid+1,r,p,R);
}
int main()
{
freopen("1.in","r",stdin);
n=read();m=read();
rep(1,n,i)
{
int x=read(),y=read();
v[x].push_back(y);
maxx=max(maxx,x);
}
rep(1,maxx,i)
{
if(!v[i].size())continue;now=i;
sort(v[i].begin(),v[i].end(),cmp);
int len=m/i,sz=v[i].size();
rep(1,len,j)sum[j]=sum[j-1]+(j>sz?0:v[i][j-1]);
for(int j=0;j<i;++j)
{
int top=0;
for(int k=j;k<=m;k+=i)s[++top]=f[k];
solve(1,top,1,top);
for(int k=j,w=1;k<=m;k+=i,++w)f[k]=g[w];
}
}
for(int i=1;i<=m;++i)printf("%lld ",f[i]);
return 0;
}