BZOJ1042 Coins - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
BZOJ1146 Network
BZOJ1927 Starrace

BZOJ1042 Coins

Hoblovski posted @ 2014年7月08日 14:00 in Solutions with tags DP 压常数 , 781 阅读
题意
4种硬币,价格在初始给出
每次询问(c1,c2,c3,c4)个硬币能有多少种方法凑成m元
 
Tag DP,爆压常数
 
容斥DP的做法挺不错的,不过蒟蒻这道题只会爆压常数的O(QM)算法
首先是个类似多重背包的问题,类比单调队列多重背包O(NM)可得到单次询问O(M)的算法
但是会超时!怎么坂呢?好像TLE不是很严重呢,能不能卡点常数过去呢(←_←!)
首先第一个硬币和最后一个是不需要完整的背包的,卡掉一半常数
其次很多公用子表达式可以减少冗余计算,卡掉四分之一常数
最后减少模运算+预判操作卡掉四分之一常数
好,过了.
 
{$INLINE ON,R-}
program bzoj1042;
 
const n=4;
      maxm=100017;
 
var f,g,s:array[0..maxm] of int64;
    r2,r3:array[0..maxm] of longint;
    m,opcnt,w1,c1,w2,c2,w3,c3,w4,c4,mdw1,mdw4,maxw:longint;
 
function min(i,j:longint):longint; inline; begin
if i<j then exit(i) else exit(j);  end;
function max(i,j:longint):longint; inline; begin
if i>j then exit(i) else exit(j);  end;
 
function dp:int64;
var i,j,k,upper:longint;
    r:^longint;
begin
fillchar(f,(m+1)<<4,0);
for j:=0 to min(c1,mdw1) do f[j*w1]:=1;
fillchar(s,sizeof(s),0); r:=@r2[0]; for j:=0 to m do begin
        inc(r); inc(s[r^],f[j]);
        k:=j-(c2+1)*w2; if k>=0 then dec(s[r^],f[k]);
        g[j]:=s[r^];
end;
fillchar(s,sizeof(s),0); r:=@r3[0]; for j:=0 to m do begin
        inc(r); inc(s[r^],g[j]);
        k:=j-(c3+1)*w3; if k>=0 then dec(s[r^],g[k]);
        f[j]:=s[r^];
end;
dp:=0; for i:=0 to min(c4,mdw4) do inc(dp,f[m-i*w4]);
end;
 
procedure work;
var i,j:longint;
begin
readln(w1,w2,w3,w4,opcnt);
for i:=1 to maxm do if r2[i-1]=w2-1 then r2[i]:=0 else r2[i]:=r2[i-1]+1;
for i:=1 to maxm do if r3[i-1]=w3-1 then r3[i]:=0 else r3[i]:=r3[i-1]+1;
maxw:=max(max(w1,w2),max(w3,w4));
while opcnt>0 do begin dec(opcnt);
        readln(c1,c2,c3,c4,m);
        mdw1:=m div w1; mdw4:=m div w4;
        writeln(dp);
end;
end;
 
begin
work;
end.

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter