roosephu試験問題の二:進制法の欲張り
2156 ワード
またリュックサックです.
ここに書いたほうがいいです.http://blog.csdn.net/huyuncong/article/details/6884369
複雑ではありません.与えられたn個のリュックサックは、m個のもので、大きさはdpを使ってはいけません.しかし、どれかの2つのものに対しては、必ず一つのものの大きさを満足させます.
ここの重要な条件は倍数関係で、進数を考慮に入れる必要があります.品物の大きさを進数として使って、最後にリュックサックの大きさをこの進数で表して、下位から高位に欲張りすればいいです.ここでhycはまだ書いてあります.上の住所に行ってみてください.
program lmd;
var
fod,num,sys,bag:array[0..1000000] of int64;
have:array[0..1000000]of int64;
tot,i,j,bj,ans,n,m:longint;
procedure inf;
begin
assign(input,'rumor.in');
assign(output,'rumor.out');
reset(input); rewrite(output);
end;
procedure ouf;
begin
close(input); close(output);
end;
procedure init;
begin
read(n,m);
for i:=1 to n do read(bag[i]);
for i:=1 to m do read(fod[i]);
end;
procedure sort(l,r:longint);
var i,j,x,tmp:longint;
begin
i:=l; j:=r; x:=fod[(l+r) shr 1];
repeat
while fod[i]<x do inc(i);
while fod[j]>x do dec(j);
if i<= j then
begin
tmp:=fod[i]; fod[i]:=fod[j]; fod[j]:=tmp;
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure prepare;
begin
sort(1,m);
tot:=0;
for i:=1 to m do
if fod[i]<>fod[i-1] then
begin
inc(tot); sys[tot]:=fod[i];
end;
fillchar(num,sizeof(num),0);
sys[tot+1]:=maxlongint;
for i:=1 to n do
begin
for j:=1 to tot do
if sys[j]>bag[i] then break
else
inc(num[j],(bag[i] mod sys[j+1]) div sys[j]);
end;
for i:=1 to tot do
have[i]:=sys[i]*num[i];
end;
procedure main;
begin
bj:=1; ans:=0;
for i:=1 to m do
begin
while ((have[bj]<fod[i]) or (sys[bj]<fod[i])) and (bj<tot) do
inc(bj);
if (have[bj]<fod[i]) or (sys[bj]<fod[i]) then break;
dec(have[bj],fod[i]); inc(ans);
end;
write(ans);
end;
begin
inf;
init;
prepare;
main;
ouf;
end.