【Vijos1250】最勇敢的机器人(并查集,分组背包DP)

发布时间:2017-5-28 20:23:28 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【Vijos1250】最勇敢的机器人(并查集,分组背包DP) ",主要涉及到【Vijos1250】最勇敢的机器人(并查集,分组背包DP) 方面的内容,对于【Vijos1250】最勇敢的机器人(并查集,分组背包DP) 感兴趣的同学可以参考一下。

题意:有N个物品,承重上限为M,有K组物品互斥关系,互斥关系有传递性,即1与2互斥,2与3互斥,1与3也互斥

给出每个物品的花费和价值,求承重上限内的最大价值总和

n<=1000,m<=1000,k<=1000

c[i]<=1000 w[i]<=10

思路:日常刷水 

因为互斥关系有传递性,并查集后就是分组背包DP

 1 var dp:array[0..1000]of longint; 2     a,c,w,f:array[1..1000]of longint; 3     n,m,i,j,k,ans,x,y,p,q:longint; 4  5 function max(x,y:longint):longint; 6 begin 7  if x>y then exit(x); 8  exit(y); 9 end;10 11 function find(k:longint):longint;12 begin13  if f[k]<>k then f[k]:=find(f[k]);14  find:=f[k];15 end;16 17 begin18  assign(input,'Vijos1250.in'); reset(input);19  assign(output,'Vijos1250.out'); rewrite(output);20 21  readln(n,m,k);22 23  for i:=1 to n do read(c[i],w[i]);24  for i:=1 to n do f[i]:=i;25  for i:=1 to k do26  begin27   readln(x,y);28   p:=find(x); q:=find(y);29   if p<>y then f[q]:=p;30  end;31  for i:=1 to n do32  begin33   q:=0;34   for j:=1 to n do35    if find(j)=i then begin inc(q); a[q]:=j; end;36   for j:=m downto 0 do37    for k:=1 to q do38     if j-w[a[k]]>=0 then dp[j]:=max(dp[j],dp[j-w[a[k]]]+c[a[k]]);39  end;40  ans:=0;41  for i:=0 to m do ans:=max(ans,dp[i]);42  writeln(ans);43 44  close(input);45  close(output);46 end.

上一篇:Java jaxp查询节点
下一篇:给用户授予权限时应该尽量避免ANY系统权限

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。