📄 数型dp2.html
字号:
懂的看一下原题吧。。。）<br>
<br>
首先，要明确一点，就是除了m=2的情况外，如果有的边的两个顶点种类相同，那么这种种类一定是第一种！这能保证解是最优的！发现了这个，就意味着问题解决了一半了。接下来就是状态表示了。。<br>
不难想到用[i,j]表示节点i，恰有j个节点被第一种类的点覆盖，总权值最小是多少。不！这还不够！我们必<br>
须增加一维！这一维不是0就是1，0表示节点i被第一种类的点覆盖，1表示节点i被非第一种类的点覆盖（就是被第二或第三...或第m种类的点覆盖啦
--！）。即状态是[i，j，0/1]怎么转移？这不禁联想到上面的第一题，如果还是这样进行一重Dp,那也就是退化成单纯的搜索了。。我们必须进行双重
Dp!!<br>
<br>
下面还是讲一下第二重的Dp:<br>
还是和上题一样，对于一个节点i，它是0或1类型的。这里只举0类型的例子（即不妨假设节点i被第一种类的点覆盖）。我们得到它的儿子的序列
1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是这个儿子类型是0,二是这个儿子的类型是
1。<br>
转移就不细讲了。因为涉及到很多很多的细节问题，并且不把这些细节问题讲清楚的话，转移就讲不清楚。而讲清楚这些细节问题至少需要1000+个字。所以就不详细展开讲了。。。。<font size="3"><strong>-_-！-_-！-_-!</strong></font>。。。。<br>
<br>
总结一下。这两道题都是TreeDp,都是需要双重Dp.可以说,它们两的本质是相同的.可是,不同在哪呢?为什么第二题《贪吃的九头龙》要再加一维呢?
深入思考,可以看出它们两的转移方式不同,即option不同.对于第一题,转移的时候是对边而言选还是不选的.对于第二题,转移的时候是对点而言选0类
型还是选1类型.而状态是记录在点上,而不是记录在边上.所以第一题只要二维而第二题要三维.换句话说,如果我们表示状态的时候把状态记录在边上,那么第
二题只要二维而第一题要三维了。上述的一段话正是本文想要说明的关键部分，有些问题虽然形式不同，但本质相同，所以只有把握本质，深入思考，才能豁然开
朗。。。。。</p></div></td></tr></tbody></table>
<br>
<div class="opt">
<a href="http://hi.baidu.com/windog18/blog/category/Acm" title="查看该分类中所有文章">类别：Acm</a>
| <a title="将此文章添加到百度搜藏" href="http://cang.baidu.com/do/add" onclick="return addToFavor();" target="_blank">添加到搜藏</a>
| 浏览(<span id="result">40</span>)
| <a href="#send">评论</a> (0)
<script language="javascript">
/*<![CDATA[*/
var pre = [true,'钩子的类型和实现', '钩子的类型和实现','/windog18/blog/item/c2a19dfa2da5ee9259ee9088.html'];
var post = [true,'(转)explicit和implicit的含义是什么？如何使用？','(转)explicit和implicit的含义是...', '/windog18/blog/item/077599d7c356bcdba144dfad.html'];
if(pre[0] || post[0]){
document.write('<div style="height:5px;line-height:5px;"> </div><div id="in_nav">');
if(pre[0]){
document.write('上一篇：<a href="' + pre[3] + '" title="' + pre[1] + '">' + pre[2] + '</a> ');
}
if(post[0]){
document.write('下一篇：<a href="' + post[3] + '" title="' + post[1] + '">' + post[2] + '</a>');
}
document.write('</div>');
}
/*]]>*/
</script><div style="height: 5px; line-height: 5px;"> </div><div id="in_nav">上一篇：<a href="http://hi.baidu.com/windog18/blog/item/c2a19dfa2da5ee9259ee9088.html" title="钩子的类型和实现">钩子的类型和实现</a> 下一篇：<a href="http://hi.baidu.com/windog18/blog/item/077599d7c356bcdba144dfad.html" title="(转)explicit和implicit的含义是什么？如何使用？">(转)explicit和implicit的含义是...</a></div>
</div>
<div class="line"> </div>
<style type="text/css">
/*<![CDATA[*/
#in_related_doc a { text-decoration:none; }
/*]]>*/
</style>
<div id="in_related_doc"><div class="tit">相关文章：</div><table border="0" cellpadding="0" cellspacing="3"><tbody><tr><td width="15"><a style="font-size: 25px;">•</a></td><td><a href="http://hi.baidu.com/westsand/blog/item/d17ff9a2dbd229aecbefd096.html" target="_blank" title="1134--最小覆盖的树型DP">1134--最小覆盖的树型DP</a> </td><td> </td><td> </td></tr></tbody></table></div><div class="line"> </div>
<script language="javascript" type="text/javascript">
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
if(arg.length <= 1) return false;
var hasMore = arg[0];
var D=function(A,B){A[A.length]=B;}
if(arg.length % 2 == 0) D(arg, ["","","",""]);
var html = ['<div id="in_related_doc"><div class="tit">相关文章：</div>'];
D(html, '<table cellpadding="0" cellspacing="3" border="0">');
for(var i = 1, j = arg.length; i < j; i += 2){
D(html, '<tr>');
D(html, '<td width="15px"><a style="font-size:25px" >•</a></td><td><a href="http://hi.baidu.com/' + arg[i][3] + '/blog/item/' + arg[i][2] + '.html" target="_blank" title="' + arg[i][0] + '">' + arg[i][1] + '</a>');
D(html, new Array(10).join('\u3000'));
D(html, '</td>');
if(arg[i + 1][0] != "")
D(html, '<td width="15px"><a style="font-size:25px" >•</a></td><td><a href="http://hi.baidu.com/' + arg[i + 1][3] + '/blog/item/' + arg[i + 1][2] + '.html" target="_blank" title="' + arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
else
D(html, '<td> </td><td> </td>');
D(html, '</tr>');
}
if(hasMore) D(html, '<tr><td colspan="4"><a target="_blank" href="/sys/search?pageno=1&type=7&sort=1&word=%CA%F7%D0%CDDP%20%BE%AD%B5%E42%CC%E2%28%D7%AA%D4%D8%29&item=b567f5597ecbdd2c2934f05e">更多>></a></td></tr>');
D(html, '</table></div><div class="line"> </div>');
var div = document.getElementById('in_related_tmp');
if(div){
div.innerHTML = html.join('');
while(div.firstChild){
div.parentNode.insertBefore(div.firstChild, div);
}
div.parentNode.removeChild(div);
}
window.setTimeout("tracker_init('in_related_doc')",100);
}
if(RelatedDocData == -1){ // not supported xhr
var script = document.createElement('script');
script.type = 'text/javascript';
script.src = '/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();
document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData == null){
GetAndEval = true;
}else{
eval(RelatedDocData);
}
/*]]>*/
</script>
<div id="in_reader">
<div class="tit">最近读者：</div>
<script>
var g_spAnnony=true;
var g_read=[
{}
];
g_read.length=g_read.length-1;
var _rh1="";
var _rh2="";
function wrreader(){
_rh1 += '<table width="100%" ><tr>';
_rh2+='<tr>';
if(g_spAnnony){
_rh1+='<td align="center" width="10%" ><img border="0" width="55" height="55" src="http://img.baidu.com/hi/img/portraitn.jpg"></td>';
_rh2+='<td> </td>';
if(g_read.length>0){
_rh1+='<td align="left" width="12%">';
}else{
_rh1+='<td align="left" width="100%">';
}
_rh1+="<a href='http://passport.baidu.com/?login&tpl=sp&tpl_reg=sp&u="+myref+"' target='_self'>登录</a>后，您就出现在这里。</td>";
_rh2+='<td> </td>'
}
if(g_read.length==0){
if(!g_spAnnony){
_rh1+='<td align=left width="100%">最近还没有登录用户看过这篇文章……</td>';
_rh2+='<td> </td>';
}
}else{
for(i=0,len=g_read.length;i<len;i++){
_rh1+='<td align="center" valign="bottom" width="10%" class="user"><a href="/'+g_read[i][0]+'" target="_blank"><img border="0" src="http://himg.baidu.com/sys/portraitn/item/'+g_read[i][1]+'.jpg"></a></td>';
_rh2+='<td align="center" valign="top" class="user"><a href="/'+g_read[i][0]+'" target="_blank">'+g_read[i][2]+'</a></td>';
}
}
_rh1+='<td width="100%"></td></tr>';
_rh2+='<td></td></tr></table>';
document.write(_rh1+_rh2);
}
wrreader();
</script><table width="100%"><tbody><tr><td width="10%" align="center"><img src="%E6%95%B0%E5%9E%8BDP2_files/portraitn.jpg" width="55" border="0" height="55"></td><td width="100%" align="left"><a href="http://passport.baidu.com/?login&tpl=sp&tpl_reg=sp&u=http://hi.baidu.com/windog18/blog/item/b567f5597ecbdd2c2934f05e%252Ehtml" target="_self">登录</a>后，您就出现在这里。</td><td width="100%"></td></tr><tr><td> </td><td> </td><td></td></tr></tbody></table>
</div>
<div class="line"> </div>
<script language="JavaScript">
allkey=allkey+"57b773cd19c40b510fb345ff_b567f5597ecbdd2c2934f05e_";
</script>
<div id="in_comment">
<a name="comment"></a>
<div class="tit">网友评论：</div>
<script>
function writecmt(type,id,cmtname,cmturl,portraitId){
var html1="";
if(type==1){
html1="<a href='"+cmturl+"' target='_blank' title='"+cmturl+"'><img border='0' src='http://himg.baidu.com/sys/portraitn/item/"+portraitId+".jpg'><br>"+cmtname+"</a>";
}else{
if(cmtname=="" || cmtname=="匿名网友"){
if(cmturl==""){
html1="<a>匿名网友</a>";
}else{
html1="<a href='"+cmturl+"' target='_blank' title='"+cmturl+"'>"+cmtname+"</a>";
}
}else{
if(cmturl==""){
html1="<div class='f14' style='display:inline'>网友:<a>"+cmtname+"</a></div>";
}else{
html1="<div class='f14' style='display:inline'>网友:<a href='"+cmturl+"' target='_blank' title='"+cmturl+"'>"+cmtname+"</a></div>";
}
}
}
document.write(html1);
}
</script>
<div id="page"></div>
</div>
<div id="in_send">
<a name="send"></a>
<form name="form1" id="popFormSubmit" action="/windog18/commit" method="post" onsubmit="return checkcmtform()">
<input name="ct" value="8" type="hidden">
<input name="cm" value="1" type="hidden">
<input name="spBlogID" value="b567f5597ecbdd2c2934f05e" type="hidden">
<script language="JavaScript">
document.write("<input type='hidden' name='spRefURL' value='"+encodeURI(window.location.href)+"'>");
</script><input name="spRefURL" value="http://hi.baidu.com/windog18/blog/item/b567f5597ecbdd2c2934f05e.html" type="hidden">
<div class="tit">发表评论：</div>
<table width="620" border="0" cellpadding="0" cellspacing="5">
<tbody><tr>
<td class="f14">姓 名：</td>
<td><input name="spBlogCmtor" id="spBlogCmtor" style="width: 220px;" onchange="checkname('spBlogCmtor')" maxlength="49" onfocus="hidErr(1);" tabindex="1" type="text">
<script>
document.write(" <a href='http://passport.baidu.com/?reg&tpl=sp&return_method=get&skip_ok=1&u=http://hi.baidu.com/sys/reg/' target='_blank'>注册</a>");
document.write(" | <a href='http://passport.baidu.com/?login&tpl=sp&tpl_reg=sp&u="+myref+"'>登录</a>");
</script> <a href="http://passport.baidu.com/?reg&tpl=sp&return_method=get&skip_ok=1&u=http://hi.baidu.com/sys/reg/" target="_blank">注册</a> | <a href="http://passport.baidu.com/?login&tpl=sp&tpl_reg=sp&u=http://hi.baidu.com/windog18/blog/item/b567f5597ecbdd2c2934f05e%252Ehtml">登录</a>
<div style="display: none;" id="nmerror">*姓名最长为50字节</div></td>
</tr>
<tr id="1_err" style="display: none;">
<td> </td>
<td><div class="error" id="1_err_con"></div></td>
</tr>
<tr>
<td class="f14">网址或邮箱：</td>
<td><input name="spBlogCmtURL" id="spBlogCmtURL" style="width: 360px;" maxlength="128" onchange="checkeandu('spBlogCmtURL')" onfocus="hidErr(2);" tabindex="2" type="text"> (选填)</td>
<script>
G("spBlogCmtor").value="";
G("spBlogCmtURL").value="";
</script>
</tr>
<tr id="2_err" style="display: none;">
<td> </td>
<td><div class="error" id="2_err_con"></div></td>
</tr>
<tr>
<td class="f14" valign="top">内 容：</td>
<td><textarea name="spBlogCmtText" id="spBlogCmtText" style="width: 520px; height: 155px;" onfocus="hidErr(3);" tabindex="3"></textarea>
<script>
G("spBlogCmtor").value=G("spBlogCmtor").defaultValue;
G("spBlogCmtText").value="";
</script>
</td>
</tr>
<tr id="3_err" style="display: none;">
<td> </td>
<td><div class="error" id="3_err_con"></div></td>
</tr>
<tr id="vercode">
<td class="f14" valign="top">验证码：</td>
<td valign="top"><input name="spVcode" value="C7F595B2B041318736919F58597B87FC12986A7E589955CF9866843BABCA8596DA80C30B8F6B216CAFBDA9E1958E6D8664A7C6A3D7AC792329C46F90DEF8C3E7" type="hidden">
<input onfocus="f_focus()" id="spVerifyKey" name="spVerifyKey" size="6" maxlength="4" autocomplete="off" tabindex="4" type="text"><br>
<script type="text/javascript">
/*<![CDATA[*/
var imgsrc="http://hiup.baidu.com/cgi-bin/genimg?C7F595B2B041318736919F58597B87FC12986A7E589955CF9866843BABCA8596DA80C30B8F6B216CAFBDA9E1958E6D8664A7C6A3D7AC792329C46F90DEF8C3E7";
function f_focus(){
if(G('yanzheng').style.display=="none" ){
G('verifypic').src=imgsrc;
G('yanzheng').style.display="block";
}
}
function newverifypic(){
G("verifypic").src = imgsrc +"&t="+ Math.random();
return false;
}
/*]]>*/
</script>
<div id="yanzheng" style="display: none;">
<img id="verifypic" width="120" height="40"><wbr><a onfocus="this.blur();" href="#" onclick="return newverifypic();" title="看不清左边的字符">看不清?</a>
</div>
</td>
</tr>
<tr>
<td class="f14" valign="top"> </td>
<td class="f14" valign="top"><input id="btn_ok" name="btn_ok" value="发表评论" tabindex="5" type="submit"></td>
</tr>
</tbody></table>
</form>
</div>
<br>
</div>
<table width="100%" border="0" cellpadding="0" cellspacing="0" height="8">
<tbody><tr><td class="modbl" width="7"> </td>
<td class="modbc"> </td>
<td class="modbr" width="7"> </td>
</tr></tbody></table>
</div>
</div>
</div>
</div>
<script language="javascript">
<!--
var hstr="/windog18/brwstat?key1=1";
document.write("<script src='"+hstr+"&key2="+allkey+"'><\/script>");
//-->
</script><script src="%E6%95%B0%E5%9E%8BDP2_files/brwstat.htm"></script>
<br><center><div id="ft">©2008 Baidu</div></center>
<script>
if(document.getElementById("m_blog"))
{
var imgarray = document.getElementById("m_blog").getElementsByTagName('img');
var imgw = document.getElementById("m_blog").offsetWidth;
imgw =imgw-40;
for(var i=0; i<imgarray.length; i++){
if(imgarray[i].className=="blogimg" && imgarray[i].width>=imgw) imgarray[i].width=imgw;
}
}
// Fix ff bugs
var blog_text = document.getElementById('blog_text');
blog_text.innerHTML = blog_text.innerHTML.replace(/href\s*=\s*("|')?(\.\.\/\.\.\/)/gi,"href=$1../$2");
</script>
</center>
<img src="%E6%95%B0%E5%9E%8BDP2_files/c.htm" style="display: none;">
</body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -