切换到宽版
发帖 回复
返回列表
  • 4236阅读
  • 0回复

提高组第二题题解 [复制链接]

 上一主题 下一主题
离线bj4sj
OIFans入门选手
 
只看楼主 倒序阅读 0 发表于: 2006-11-20
终于弄出来了
告别NOI........
高三努力......
大致思路:把zj个主件和m-zj个附件打成num个包,f[i,j]表示处理完前i个主件还剩j元时获得的最大权值
占用内存2232KB

复制代码
  1. // program NOIP2006_2:Budget
  2. // by bj4sj
  3. const
  4. maxn=3500;
  5. maxm=60;
  7. var
  8. v,w,p:array[1..maxm] of integer;
  9. son:array[1..maxm,1..2] of integer;
  10. fq,jg,qz:array[1..maxm] of integer;
  11. i,zj,num,numm,m:integer;
  12. N,max:integer;
  13. f:array[0..4*maxm,0..maxn] of integer;
  15. procedure init;//输入数据,并转化数据,成为背包问题
  16. var
  17. i,j,k:integer;
  18. begin
  19. assign(input,'budget.in');
  20. reset(input);
  21. read(N,m);
  22. n:=n div 10;
  23. zj:=0;
  24. for i:=1 to m do
  25. begin
  26.   read(v[i],w[i],fq[i]);
  27.   v[i]:=v[i] div 10;
  28.   if fq[i]=0 then
  29.   begin
  30.     inc(zj);//主件个数
  31.     son[zj,1]:=-1;//儿子编号指针
  32.     son[zj,2]:=-1;
  33.     p[zj]:=i;//主件编号指针
  34.   end
  35.   else
  36.   begin
  37.   for k:=1 to zj do if p[k]=fq[i] then fq[i]:=k;
  38.   if son[fq[i],1]=-1 then son[fq[i],1]:=i else son[fq[i],2]:=i;
  39.   end;
  40. end;
  41. num:=0;
  42. for i:=1 to zj do
  43. begin
  44.   inc(num);
  45.   qz[num]:=v[p[i]]*w[p[i]]; //第num个包的权值(只含主件)
  46.   jg[num]:=v[p[i]]; //价格
  47.   for k:=1 to 2 do
  48.   begin
  49.     if son[i,k]<>-1 then
  50.     begin
  51.     inc(num);
  52.     qz[num]:=v[p[i]]*w[p[i]]+v[son[i,k]]*w[son[i,k]]; //第num个包的权值(含主件和第K个附件)
  53.     jg[num]:=v[p[i]]+v[son[i,k]];
  54.     end;
  55.   end;
  56.   if son[i,2]<>-1 then
  57.   begin
  58.     inc(num);
  59.     qz[num]:=v[p[i]]*w[p[i]]+v[son[i,1]]*w[son[i,1]]+v[son[i,2]]*w[son[i,2]];//第num个包的权值(含主件和2个附件)
  61.     jg[num]:=v[p[i]]+v[son[i,1]]+v[son[i,2]];
  62.   end;
  63. end;
  64. close(input);
  65. end;
  67. procedure slove;
  68. var
  69. i,j,k:integer;
  70. tmp:array[1..6] of integer;
  71. begin
  72. for i:=0 to 4*maxm do
  73.   for j:=0 to maxn do f[i,j]:=-20000;
  74. for j:=0 to n do f[0,j]:=0;
  75. num:=0;
  76. for i:=1 to zj do //解决背包问题,每个主件只能选一次.究竟选哪个则需要看tmp[1..6]的大小
  77. begin
  78.   for j:=0 to N do
  79.   begin
  80.     numm:=num;
  81.     for k:=4 to 6 do tmp[k]:=-20000;
  82.     tmp[1]:=f[i-1,j];
  83.     tmp[2]:=f[i,j];
  84.     inc(num);
  85.     tmp[3]:=f[i-1,j+jg[num]]+qz[num];
  86.     if son[i,1]<>-1 then
  87.     begin
  88.     inc(num);
  89.     tmp[4]:=f[i-1,j+jg[num]]+qz[num];
  90.     end;
  91.     if son[i,2]<>-1 then
  92.     begin
  93.     inc(num);
  94.     tmp[5]:=f[i-1,j+jg[num]]+qz[num];
  95.     inc(num);
  96.     tmp[6]:=f[i-1,j+jg[num]]+qz[num];
  97.     end;
  98.     max:=-20000;
  99.     for k:=1 to 6 do
  100.     begin
  101.     if max<tmp[k] then max:=tmp[k];
  102.     end;
  103.     f[i,j]:=max;
  104.     if j<>n then num:=numm;
  105.   end;
  106. end;
  107. end;
  109. begin
  110. init;
  111. slove;
  112. max:=-20000;
  113. for i:=0 to n do
  114. begin
  115.   if max<f[zj,i] then max:=f[zj,i];
  116. end;
  117. assign(output,'budget.out');
  118. rewrite(output);
  119. writeln(max*10:1);
  120. close(output);
  121. end.
[ 此贴被bj4sj在2006-11-20 01:25重新编辑 ]
回复
举报
分享到 淘江湖 新浪 QQ微博 QQ空间 开心 人人 豆瓣 网易微博 百度 鲜果 白社会 飞信
发帖 回复
返回列表
快速回复
限100 字节
 
上一个 下一个