【POJ1276】Cash Machine（多重背包单调队列优化）

大神博客转载http://www.cppblog.com/MatoNo1/archive/2011/07/05/150231.aspx
多重背包的单调队列初中就知道了但一直没（不会）写
二进制优化初中就写过
一直不写会心虚就写一下这个吧
朴素方程
dp[i,j]=max(dp[i-1,j-w[i]*k]+c[i]*k) w[i]*k<=j k<=j div w[i]
忽略第一维
dp[j]=max(dp[j-w[i]*k]+c[i]*k)
复杂度O(m2n)
以下是大神原文：
将决策下标按照模w0的余数进行分类，可以分成w0类，分别对应模w0余0、余1……余(w0-1)的情况。这时，上面方程中的所有决策下标j-x*w0都是同一类的。进一步，设q =j/w0（下取整），r=j%w0，则j=q*w0+r，对于某个决策下标j'，设k=(j'-r)/w0，即j'=k*w0+r。显然可以发现，k的取值范围是：k>=0且q-s0<=k<=q，也即k的下界是max{0, q-s0}——随j的单调而单调。
然后，转移方程可以改为（这里把r当成一个已知量了）：
F[q*w0+r] = max{F[k*w0+r]+(q-k)*v0} (k>=0且q-s0<=k<=q)
即F[q*w0+r]=max{F[k*w0+r]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
设G[k]=F[k*w0+r]得：
G[q]=max{G[k]-k*v0}+q*v0 (k>=0且q-s0<=k<=q)
这个方程已经可以使用单调队列来优化了！

这样可以得出算法：
（1）从1到n，枚举i，建立w[i]个空的单调队列，每个队列的元素都是两个int值：(k, val)，表示转换后下标和决策值(G[k]-k*v[i])；
（2）从0到m，枚举j，得出q、r的值，对于队列r：
【1】删去队首过时（k<q-m[i]）的元素；
【2】F[j]入队（这里的F[j]指上一阶段的F[j]，即F[i-1][j]。因此这一步操作一定要先进行），删去队尾所有决策值val不大于(F[j]-q*v[i])的元素。
【3】取出队首结点，其val值加上q*v[i]后即为本阶段F[j]的值。
最后F[m]即为结果。总时间复杂度为O(NM)。

其实这个是可以推广的，即对于如下形式的转移方程（其中H、G和W均为常量，B[i]为决策下标的下界，随i单调）：
F[i] = opt{F[i-x*H+W]}+G (B[i]<=i-x*H+W<i，x∈N）
都可以用上述的办法进行转化，从而进行单调队列优化。

我自己的萎靡过程：
形如dp[i]=max(dp[j]+cost(j+1,i))+M,cost具有单调性的DP可以用单调队列优化
我们尝试转化它的形式
dp[j]=max(dp[j-w[i]*1]+c[i]*1,dp[j-w[i]*2]+c[i]*2])……
设k<j<i,i-j,i-k能整除w[i]，显然j-k也可以
dp[j]+c[i]*(i-j)/w[i]>dp[k]+c[i]*(i-k)/w[i]
dp[j]-dp[k]>c[i]*(i-k-i+j)/w[i]
dp[j]-dp[k]>c[i]*(j-k)/w[i]
好像很麻烦的样子

好吧还是学大神的做法吧
设j=w[i]*k+r,r=j mod w[i]
dp[w[i]*k+r]=max(dp[w[i]*(k-x)+r]+c[i]*x)
设x>y,dp[w[i]*x+r]+c[i]*x>dp[w[i]*y+r]+c[i]*y
dp[w[i]*x+r]-dp[w[i]*y+r]>c[i]*(y-x)
(dp[w[i]*x+r]-dp[w[i]*y+r])/(y-x)>c[i]对于单个i成立
我们对于每个j计算出它对于每个i时的max x与r O(mn)
之后就可以用单调队列的思路做了

POJ上一直RE不知道怎么回事搞得我都不知道对不对

自己的对拍好像没有问题

哪位找到错误提醒下谢谢

一些奇奇怪怪的if 判 a[i] k 什么的不加会有奇奇怪怪的错误

显然空间不够必须滚动队列

POJ空间也卡格式也卡

懒得改了反正没什么乱用

 var q:array[..,..,..]of longint;

     f:array[..,..]of longint;

     t,w:array[..]of longint;

     a,ww,cc:array[..]of longint;

     m,n,i,j,k,r,t1,w1,tmp,ans,v:longint;

 begin

  assign(input,'1.in'); reset(input);

  assign(output,'1.out'); rewrite(output);

  while not eof do

  begin

   read(m,n);

   if (m=)and(n=) then break;

   for i:= to n do

   begin

    read(a[i],ww[i]);

    cc[i]:=ww[i];

    if a[i]>m div ww[i] then a[i]:=m div ww[i];

   end;

   fillchar(f,sizeof(f),); ans:=;

   for i:= to n do

   if a[i]> then

   begin

    v:=-v;

    fillchar(q,sizeof(q),);

    for j:= to m do f[v,j]:=f[-v,j];

    for j:= to ww[i]- do begin w[j]:=; t[j]:=; end;

    for j:= to m do

    begin

     k:=j div ww[i];

     if k>a[i] then continue; r:=j mod ww[i];

     inc(w[r]); q[r,w[r] mod ,]:=k; q[r,w[r] mod ,]:=f[-v,j]-k*ww[i];

    end;

    for j:= to m do

    begin

     k:=j div ww[i]; r:=j mod ww[i];

     t1:=t[r]; w1:=w[r];

     while (w1-t1>=)and(k-q[r,t1 mod ,]>a[i]) do

     begin

      inc(t[r]); inc(t1);

     end;

      tmp:=q[r,t1 mod ,]+cc[i]*k;

     if tmp>ans then ans:=tmp;

     if tmp>f[v,j] then f[v,j]:=tmp;

     while (w1-t1>=)and(q[r,w1 mod ,]<=f[-v,j]-k*ww[i]) do

      begin dec(w[r]); dec(w1); end;

     

      inc(w[r]); inc(w1); q[r,w1 mod ,]:=k; q[r,w1 mod ,]:=f[-v,j]-k*ww[i];

    end;

   end;

   writeln(ans);

  end;

  close(input);

  close(output);

 end.

巴特西

【POJ1276】Cash Machine（多重背包单调队列优化）

最新文章

热门文章