这样染一遍色（刷一遍数组），每类钞票不管几张都耗时O(cash)总耗时O(10*cash)撑死一百万啊……
不就解决了么？
var
 f:array[0..101000]of boolean;
 v:array[0..101000]of integer;
 n,m,max,a,b,i,j:longint;
begin
 repeat
  read(m,n);
  fillchar(f,sizeof(f),0);
  f[0]:=true;
  max:=0;
  for i:=1 to n do
   begin
    read(a,b);
    inc(max,a*b);
    if max>m-b then max:=m-b;
    fillchar(v,sizeof(v),0);
    for j:=0 to max do
     if f[j] and(v[j]<a)and not f[j+b] then
      begin
       f[j+b]:=true;
       v[j+b]:=v[j]+1;
      end;
   end;
  for i:=m downto 0 do
   if f[i] then begin writeln(i); break; end;
 until seekeof;
end.

• Re:看到很多人写的很长，什么二进制优化是啥玩意，有那么麻烦么？ (718) jayhaizeizai 2011-08-17 12:05:14
• 多重背包转化为01背包，我的63ms才过，换成完全背包再写下。。。 (0) lijingwei 2011-08-17 14:20:33
  • Re:多重背包转化为01背包，我的63ms才过，换成完全背包再写下。。。 (1130) jayhaizeizai 2011-08-17 14:41:03
    • Re:多重背包转化为01背包，我的63ms才过，换成完全背包再写下。。。 (82) lijingwei 2011-08-17 15:05:51
      • Re:多重背包转化为01背包，我的63ms才过，换成完全背包再写下。。。 (98) jayhaizeizai 2011-08-17 15:13:50
        • Re:多重背包转化为01背包，我的63ms才过，换成完全背包再写下。。。 (567) lijingwei 2011-08-17 15:16:48