【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[0..1000,0..1000,1..2]of longint;
    f:array[0..1,0..100000]of longint;
    t,w:array[0..20000]of longint;
    a,ww,cc:array[1..100]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=0)and(n=0) then break;
  for i:=1 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),0); ans:=0;
  for i:=1 to n do
  if a[i]>0 then
  begin
   v:=1-v;
   fillchar(q,sizeof(q),0);
   for j:=0 to m do f[v,j]:=f[1-v,j];
   for j:=0 to ww[i]-1 do begin w[j]:=1; t[j]:=1; end;
   for j:=0 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 1000,1]:=k; q[r,w[r] mod 1000,2]:=f[1-v,j]-k*ww[i];
   end;

   for j:=0 to m do
   begin
    k:=j div ww[i]; r:=j mod ww[i];
    t1:=t[r]; w1:=w[r];
    while (w1-t1>=1)and(k-q[r,t1 mod 1000,1]>a[i]) do
    begin
     inc(t[r]); inc(t1);
    end;

     tmp:=q[r,t1 mod 1000,2]+cc[i]*k;
    if tmp>ans then ans:=tmp;
    if tmp>f[v,j] then f[v,j]:=tmp;


    while (w1-t1>=0)and(q[r,w1 mod 1000,2]<=f[1-v,j]-k*ww[i]) do
     begin dec(w[r]); dec(w1); end;

    
     inc(w[r]); inc(w1); q[r,w1 mod 1000,1]:=k; q[r,w1 mod 1000,2]:=f[1-v,j]-k*ww[i];
 
   end;
  end;
  writeln(ans);

 end;
 close(input);
 close(output);
end.