📄 数型dp2.html
字号:
<html><head><!--STATUS OK-->
<meta http-equiv="content-type" content="text/html; charset=GB2312"><title>树型DP 经典2题(转载)_想飞</title>
<style>.error{color:#FF0000;font-size:12px}</style>
<script type="text/javascript" src="%E6%95%B0%E5%9E%8BDP2_files/global.js"></script>
<script language="javascript" src="%E6%95%B0%E5%9E%8BDP2_files/popup.js"></script>
<script language="JavaScript" src="%E6%95%B0%E5%9E%8BDP2_files/g_spjs.js"></script>
<script language="javascript">
<!--
var allkey="";
var i=0;
var flag=0;
function setpv(allnum)
{
var num = allnum.split('_');
document.getElementById("result").innerHTML=num[0];
}
function checkMail(s)
{
var pattern=/\w+@\w+\.[a-z]+/;
if(pattern.test(s))
{
return true;
}
else
{
return false;
}
}
function checkeandu(eanduid)
{
var eanduvalue=G(eanduid).value;
var len=bytes(eanduvalue);
if(len>128)
{
showErr(2,"您输入的网址或邮箱太长，请保持在128字节以内。");
return false;
}
else
{
return true;
}
}
function cmtdel(str)
{
var pop=new Popup({ contentType:3,isReloadOnClose:false,width:340,height:80});
pop.setContent("title","删除评论");
pop.setContent("confirmCon","您确定要彻底删除这条评论吗？");
pop.setContent("callBack",delCallback2);
pop.setContent("parameter",{fid:str,popup:pop});
pop.build();
pop.show();
return false;
}
function delCallback2(para)
{
var o_pop=para["popup"];
o_pop.config.contentType=1;
o_pop.setContent("contentUrl","");
o_pop.reBuild();
G(para["fid"]).target=o_pop.iframeIdName;
eval("document."+para["fid"]).submit();
}
function checkname(strid)
{
var ele=document.getElementById(strid);
var len=bytes(ele.value);
if(len>49)
{
showErr(1,"您输入的姓名太长，请保持在49字节以内。");
return false;
}
else
{
if(len==0)
{
document.getElementById(strid).value="匿名网友";
}
return true;
}
}
function checktext(textid)
{
document.getElementById(textid).value=trimlr(textid);
var str=trimrn(textid);
len=str.length;
if(len==0 || ((/^[\s, ]+$/gi).test(str)) )
{
showErr(3,"您必须输入评论内容，请检查。");
return false;
}
else
{
if(len>1000)
{
showErr(3,"您输入的评论内容太长，请保持在500字以内。");
return false;
}
return true;
}
}
function showErr(index,str)
{
G(index+"_err").style.display="";
G(index+"_err_con").innerHTML=str;
}
function hidErr(index)
{
G(index+"_err").style.display="none";
G(index+"_err_con").innerHTML="";
}
function alertPop(tit,con)
{
var pop=new Popup({ contentType:4,isReloadOnClose:false,width:340,height:80});
pop.setContent("title",tit);
pop.setContent("alertCon",con);
pop.build();
pop.show();
}
function cmtfull()
{
var cnum=0;
if(cnum>=50000)
{
alertPop("发表评论","单篇日志评论数最多为50000条.");
return false;
}
else
{
return true;
}
}
function checkcmtform()
{
if(checkname("spBlogCmtor")&&checkeandu("spBlogCmtURL")&&checktext("spBlogCmtText")&&cmtfull())
{
submitForm();
return true;
}
else
{
return false;
}
}
var g_pop=null;
function submitForm()
{
g_pop=new Popup({ contentType:1,isReloadOnClose:false,width:340,height:80});
g_pop.setContent("title","添加评论");
g_pop.setContent("contentUrl","");
g_pop.setContent("someDisabledBtn","btn_ok");
g_pop.build();
G("popFormSubmit").target=g_pop.iframeIdName;
g_pop.show();
}
function g_close_pop()
{
g_pop.close();
}
function formatonlinpic()
{
var picobj=document.getElementsByName("onlinepic");
var picnum=picobj.length;
for(var i=0;i<picnum;i++)
{
if(picobj[i].width>200)
{
picobj[i].width=200;
}
if(picobj[i].height>200)
{
picobj[i].height=200;
}
}
}
function addToFavor(){
var blogTitle='树型DP 经典2题(转载)'.replace(/'/g,'\'');
window.open('http://cang.baidu.com/do/add?it='+encodeURIComponent(blogTitle+'_百度空间')+'&iu='+encodeURIComponent(location.href)+'&fr=sp#nw=1','_s','scrollbars=no,width=600,height=450,right=75,top=20,status=no,resizable=yes');
return false;
}
var isIE = /*@cc_on!@*/false;
function tracker(did,a){
return function(){
var t=new Date().getTime();
var href=a.href;
if(isIE){
var r = /href\s*=\s*("|')?([^\s]*)\1/gi;
if(r.test(a.outerHTML))
href = RegExp.$2;
}
new Image().src = "http://hi.baidu.com/sys/statlog/1.gif?m=" + did + "&v=" + encodeURIComponent(href) + "&c=" + encodeURIComponent(location.href) + "&t="+t;
}
}
function tracker_init(did){
var _s=document.getElementById(did);
var as = _s.getElementsByTagName('A');
for(var i = 0, j = as.length; i < j; i ++){
var a = as[i];
if(isIE){
a.attachEvent("onclick", tracker(did,a));
}else{
a.addEventListener("click", tracker(did,a), false);
}
}
}
//-->
</script>
<script type="text/javascript">
/*<![CDATA[*/
var RelatedDocData = null, GetAndEval = false;
(function(){
var xhr = BdAjax.getXHR();
if(xhr == null){
RelatedDocData = -1;
return;
}
xhr.open("GET", "/sys/search?type=8&word=%CA%F7%D0%CDDP%20%BE%AD%B5%E42%CC%E2%28%D7%AA%D4%D8%29&item=b567f5597ecbdd2c2934f05e&t=" + new Date().getTime(), true);
xhr.onreadystatechange = function(){
if(xhr.readyState == 4){
if(xhr.status == 0 || xhr.status == 200){
if(GetAndEval){
eval(xhr.responseText);
}else{
RelatedDocData = xhr.responseText;
}
}
}
}
xhr.send(null);
})();
/*]]>*/
</script>
</head><body onload="formatonlinpic();">
<center>
<script type="text/javascript">
/*<![CDATA[*/
if(top.location != self.location){
top.location = self.location;
}
var myref = encodeURI("http://hi.baidu.com/windog18/blog/item/b567f5597ecbdd2c2934f05e%2Ehtml");
/*]]>*/
</script>
<link rel="stylesheet" type="text/css" href="%E6%95%B0%E5%9E%8BDP2_files/mods.css">
<link rel="stylesheet" type="text/css" href="%E6%95%B0%E5%9E%8BDP2_files/7275c643d9e5e6119313c601.css">
<link rel="stylesheet" type="text/css" href="%E6%95%B0%E5%9E%8BDP2_files/space.css">
<style type="text/css">
/*<![CDATA[*/
#usrbar{padding:4px 10px 3px 0;font-size:12px;height:19px;line-height:19px;color:#000000;font-family:Arial;text-align:right;background:#ffffff;filter:alpha(opacity=65);-moz-opacity:0.5;width:auto !important;width:100%;letter-spacing:normal}
#usrbar a,#usrbar a:link,#usrbar a:visited{color:#0000CC;text-decoration:underline}
#ft{clear:both;height:20px;line-height:20px;color:#666666;font-size:12px;font-family:Arial;text-align:center}
#ft a,#ft a:link,#ft a:visited{color:#7777CC;text-decoration:underline}
#usrbar,#usrbar a,#usrbar a:link,#usrbar a:visited,#ft,#ft a,#ft a:link,#ft a:visited{letter-spacing:normal}
/*]]>*/
</style>
<div id="usrbar"><nobr>
<a href="http://www.baidu.com/" target="_blank">百度首页</a>
| <a id="hi_index" href="http://hi.baidu.com/" target="_blank">百度空间</a>
<script type="text/javascript">
document.write('| <a href="http://passport.baidu.com/?login&tpl=sp&tpl_reg=sp&u=http://hi.baidu.com' + encodeURI('/windog18/blog/item/b567f5597ecbdd2c2934f05e%2Ehtml') + '">登录</a>');
</script>| <a href="http://passport.baidu.com/?login&tpl=sp&tpl_reg=sp&u=http://hi.baidu.com/windog18/blog/item/b567f5597ecbdd2c2934f05e%252Ehtml">登录</a>
</nobr></div>
<div id="main" align="left">
<!--[if IE]>
<script>
var objmain = document.getElementById("main");
function updatesize(){ var bodyw = window.document.body.offsetWidth; if(bodyw <= 790) objmain.style.width="772px"; else if(bodyw >= 1016) objmain.style.width="996px"; else objmain.style.width="100%"; }
updatesize(); window.onresize = updatesize;
</script>
<![endif]-->
<div id="header">
<div class="lc"><div class="rc"></div></div>
<div class="tit"><a href="http://hi.baidu.com/windog18" class="titlink" title="windog18的空间 http://hi.baidu.com/windog18">想飞</a></div>
<div class="desc">飞翔吧~~~</div>
<div id="tabline"> </div>
<div id="tab"><a href="http://hi.baidu.com/windog18">主页</a><a href="http://hi.baidu.com/windog18/blog" class="on">博客</a><a href="http://hi.baidu.com/windog18/album">相册</a><span>|</span><a href="http://hi.baidu.com/windog18/profile">个人档案</a>
<span>|</span><a href="http://hi.baidu.com/windog18/friend">好友</a>
</div>
</div>
<div class="stage">
<div class="stagepad">
<div style="width: 100%;">
<table class="modth" width="100%" border="0" cellpadding="0" cellspacing="0">
<tbody><tr><td class="modtl" width="7"> </td>
<td class="modtc" nowrap="nowrap"><div class="modhead"><span class="modtit">查看文章</span></div></td>
<td class="modtc" align="right" nowrap="nowrap"></td>
<td class="modtr" width="7"> </td>
</tr></tbody></table>
<div id="m_blog" class="modbox">
<div class="tit">树型DP 经典2题(转载)</div>
<div class="date">2008-07-19 11:26</div>
<table style="table-layout: fixed;"><tbody><tr><td><div id="blog_text" class="cnt"><p><font size="3"><strong>题目一：道路重建(USACO_2002_Feb02 Rebuilding Roads)（PKU1947）</strong></font>(程序附后)<br>
题目大意是给一棵树，要去掉最少的边，使一棵子树从中分离出来，且这棵子树要恰有B个节点。<br>
<br>
很容易想到此题为树型Dp,用状态[i,j]来表示以节点i为根，得到一棵j个节点的子树至少要去多少条边（请注<br>
意，这里定义的节点i是这棵子树的根,所以一定包含这棵去掉一些边后所得到的j个节点的子树里面）。怎么<br>
转移呢？如果穷举i的子节点保留还是不保留，如果保留，保留多少个。那么这道题目又退化成完全的搜索了。。不难想到,因为节点i的所有子节点是一个线性结构,我们可以双重Dp!!<br>
<br>
下面讲一下第二重的Dp:<br>
对于一个节点i,<br>
设它的儿子依次为1,2,....,x.再设一个状态(k,m)表示到节点i的第k个儿子,要保留m个节点,至少要去掉多少条边.这样,对于这个节点i,
我们得到它的儿子的序列1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是选这个k,二是不选
这个k,<br>
1.如果不选k,那么(k-1,m)+1--->(k,m)(加1是因为不选这个儿子k,所以k和i所连的边应该断开,那么花费就要加1).<br>
2.如果选nk,那么(k-1,j)+[k,m-j]--->(k,m)(注意,中括号所表示的状态时第一重动规所得到的状态,在这里[k,m-j]的意思就是节点k为根，得到一棵(m-j)个节点的子树至少要去多少条边)</p>
<p>那么就很容易转移了:(k,m)=min{(k-1,j)+[k,m-j]{0<=j<=m},(k-1,m)+1},边界自己想
吧。。。。。对于这个节点i,算完所有的(1,m),(2,m),...,(x,m)后,[i,m+1]就等于(x,m)(这里+1是因为i这个节点要保
留),每次算出(i,B)后,动态更新下ans就行了...Dp时候的顺序可以记忆化搜索,也可以按后序遍历的顺序进行Dp...</p>
<p>尽管讲了这么多,感觉还是有很多细节问题没有讲清楚,这还是要自己思考一下的,这里只是提供了一个大致的<br>
思路而已...(更多时候，这个思路可能只有作者本人才能看懂的<font size="4"><strong>--!</strong></font>)。如果谁有更好的方法,欢迎留言<strong><font size="4">:)</font></strong></p>
<p><strong><font size="3">题目二： 贪吃的九头龙（NOI2002_DAY1）</font></strong><br>
题目大意是给一棵树，再给m种点，这些点要覆盖这棵树的所有节点，且每种种类的点至少要用一次，还规定第一种点必须恰好用K次。这棵树的每一条边都有一个
权值（每条边的权值可能不同）。对于某条边，若这条边的两个顶点种类相同，则总权值需要加上这条边的权值。问总权值最少是多少。（可能描述的有些模糊，不
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -