【题意】
有b(<=5)种物品,每种编号为c,有k个,单价p元,现有s种组合,每种包含n种物品,给定n种物品的编号c,每种所需k,以及组合价格p
求购买所有物品所需最小费用
【输入】
第一行b
接下来b行每行三个数c、k、p
之后一行一个s
接下来s行每行描述一个组合
【输出】
最小费用
b和s很小,所以状态压缩一下,记忆化搜一下就行
program poj1170; var s,c,b,n,i,j,k:longint; six:array [0..7] of longint; num:array [0..1000] of longint; left,pri:array [0..6] of longint; p:array [0..99] of longint; com:array [0..99,0..6] of longint; f:array [0..7777] of longint; yes:array [0..7777] of boolean; function min (a,b:longint):longint;inline; begin if a<b then exit(a) else exit(b); end; function search (status:longint):longint; var i,j,k:longint; begin if yes[status] then exit(f[status]); f[status]:=maxlongint; for i:=1 to s do begin k:=status; for j:=1 to b do if status div six[j-1] mod 6>=com[i,j] then k:=k-com[i,j]*six[j-1] else break; if status div six[j-1] mod 6<com[i,j] then continue; f[status]:=min(f[status],search(k)+p[i]); end; for i:=1 to b do if status div six[i-1] mod 6>0 then f[status]:=min(f[status],search(status-six[i-1])+pri[i]); yes[status]:=true; exit(f[status]); end; begin read(b); for i:=1 to b do begin read(c,left[i],pri[i]); num[c]:=i; end; read(s); for i:=1 to s do begin read(n); for j:=1 to n do begin read(c,k); com[i,num[c]]:=com[i,num[c]]+k; end; read(p[i]); end; six[0]:=1; for i:=1 to 7 do six[i]:=six[i-1]*6; k:=0; for i:=1 to b do k:=k+left[i]*six[i-1]; fillchar(yes,sizeof(yes),false); yes[0]:=true; f[0]:=0; writeln(search(k)); end.