魔兽地图
DotR/.IN/.OUT/.PAS/.EXE
【题意】
多层多附件背包问题,求能获得的最大价值以及方案
【输入】
第一行n(n<=51)、m(m<=2000),表示物品数量和所拥有的钱数
接下来n行,每行第一个数字表示该种物品的价值
之后是一个字母
A表示这件物品是一个合成物品,接下来是一个数字c,表示由c种物品合成,之后的c对数字分别表示物品编号和所需数量
B表示这件物品是一个基础物品,之后两个数字分别是单价cost和数量left(数量小于等于100)
【输出】
第一行一个数字表示最大价值
接下来n行每行一个数字表示该种物品购买量
对于求最大价值,用f[i][j][k]表示第i件物品卖j件花k元钱的所能获得最大价值
然后树形动规做背包,这里牵扯到一个优化,用数组max[i][j][k]表示第i件物品花k元至少买j件的最优情况是买多少件
这样树形动规的复杂度大概为O(n left m^2)
这是最大复杂度,因为背包问题一向冗余状态比较多,所以加上一些常数优化便可以在规定的5s内完成
比如说统计该节点子树总和、该种物品最多购买量、完成条件最小花费等……
我的dp最慢一个点也不超过三秒
之后是非常纠结的输出方案
我采取了将最优方案[x][y][z]分解
对于每个节点重新做一遍背包,记录每个节点加入后的状态
然后反向枚举每个节点所用的花费,如果可行则记录
这个复杂度相对于之前的树归可以忽略不计了……
program dotr; type arr=array [0..2001] of longint; var pp,oo,c,top,ans,tot,n,m,i,j,k,a,b:longint; sum,need,dd,root,value,cost,left:array [0..51] of longint; next,point,count:array [0..3001] of longint; max,f:array [0..51,0..101] of arr; h:array [0..51] of arr; cop:arr; space,order:char; function min (a,b:longint):longint;inline; begin if a<b then exit(a) else exit(b); end; function more (a,b:longint):longint;inline; begin if a>b then exit(a) else exit(b); end; procedure connect (a,b,c:longint);inline; begin inc(tot); point[tot]:=b; count[tot]:=c; next[tot]:=root[a]; root[a]:=tot; end; procedure calcmax(now:longint);inline; var i,j:longint; begin for i:=0 to sum[now] do max[now,left[now],i]:=left[now]; for i:=left[now]-1 downto 0 do for j:=0 to sum[now] do if f[now,i,j]>=f[now,max[now,i+1,j],j] then max[now,i,j]:=i else max[now,i,j]:=max[now,i+1,j]; end; procedure dfs (now:longint); var i,j,k,q,p:longint; begin if root[now]=0 then begin sum[now]:=cost[now]*left[now]; if sum[now]>m then sum[now]:=m; for i:=1 to left[now] do for j:=cost[now]*i to sum[now] do f[now,i,j]:=value[now]*i; calcmax(now); exit; end; cost[now]:=0; left[now]:=100; sum[now]:=0; k:=root[now]; while k<>0 do begin dfs(point[k]); sum[now]:=sum[now]+sum[point[k]]; if left[now]>left[point[k]] div count[k] then left[now]:=left[point[k]] div count[k]; cost[now]:=cost[now]+cost[point[k]]*count[k]; k:=next[k]; end; if sum[now]>m then sum[now]:=m; for i:=0 to left[now] do begin k:=root[now]; while k<>0 do begin cop:=f[now,i]; for q:=i*count[k]*cost[point[k]] to sum[point[k]] do for p:=sum[now] downto i*cost[now]+q-i*count[k]*cost[point[k]] do if f[now,i,p]< cop[p-(q-i*count[k]*cost[point[k]])]+ f[point[k],max[point[k],i*count[k],q],q]- i*count[k]*value[point[k]] then f[now,i,p]:=cop[p-(q-i*count[k]*cost[point[k]])]+ f[point[k], max[point[k],i*count[k],q],q]- i*count[k]*value[point[k]]; k:=next[k]; end; for j:=i*cost[now] to sum[now] do f[now,i,j]:=f[now,i,j]+i*value[now]; end; calcmax(now); end; procedure search (now,num,money:longint); var i,j,k,o,q,p,tot,z:longint; xl,a,b,c:array [0..51] of longint; begin need[now]:=need[now]+num; if num*cost[now]=money then exit; if root[now]=0 then exit; o:=0; fillchar(h,sizeof(h),0); k:=root[now]; while k<>0 do begin inc(o); xl[o]:=k; need[point[k]]:=need[point[k]]-num*count[k]; for q:=num*count[k]*cost[point[k]] to sum[point[k]] do for p:=sum[now] downto num*cost[now]+q-num*count[k]*cost[point[k]] do if h[o,p]< h[o-1,p-(q-num*count[k]*cost[point[k]])]+ f[point[k], max[point[k],num*count[k],q], q]-value[point[k]]*count[k]*num then h[o,p]:=h[o-1,p-(q-num*count[k]*cost[point[k]])]+ f[point[k], max[point[k],num*count[k],q],q] -value[point[k]]*count[k]*num; k:=next[k]; end; z:=money; tot:=o; while o>0 do begin k:=xl[o]; for i:= num*count[k]*cost[point[k]] to sum[point[k]] do if h[o,z]= h[o-1,z-(i-num*count[k]*cost[point[k]])]+ f[point[k],max[point[k],num*count[k],i],i]- value[point[k]]*num*count[k] then begin a[o]:=point[k]; b[o]:=max[point[k],num*count[k],i]; c[o]:=i; break; end; z:=z-(i-num*count[k]*cost[point[k]]); dec(o); end; for o:=1 to tot do search(a[o],b[o],c[o]); end; begin read(n,m); for i:=1 to n do begin read(value[i]); read(space); read(order); if order='A' then begin read(c); for j:=1 to c do begin read(a,b); connect(i,a,b); inc(dd[a]); end; end else read(cost[i],left[i]); readln; end; for top:=1 to n do if dd[top]=0 then break; dfs(top); ans:=f[top,max[top,0,sum[top]],sum[top]]; writeln(ans); end.