注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

树形DP小结  

2012-04-02 20:55:02|  分类: 学习小结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       最近在搞DP,从一般的DP水题到凸完全性单调优化再到树形DP之类的,系统的过了一遍,总算是有一点感觉了,决定把这段时间从网上抓来的乱七八糟的题目合起来写个题解,就当是阶段性小结吧,先从树形DP开始。
       
       一直感觉树形DP的题目都差不多,就是在一棵树上搞来搞去嘛,难一点再加一个背包什么的,不像一般的其他的DP那样,很多时候连它是个DP都不知道,但貌似有大神说过树形DP最难?估计我还没到那个境界吧- -
       
       水题,求一颗树的最小点覆盖,这题其实可以用贪心,每次先把子结点只有叶子的点给染色,不过我太懒了,就直接写了一个树形DP水过去了。

       水题,随便选一个点做根,然后算出每个节点的以子结点子树的总节点个数,判断有没有超过一半,最后再判断父亲节点。

       一道阅读题,题目用了一点璋眼法,发现是一棵树就行了。

       也是水题,类似tree cutting。

       给定一棵树,对每个点求树上所有点中离它最远的距离S[i]。先随便选一个点做根dfs一遍,预处理出f[i],f[i]表示以i为根的子树节点中离i最远的距离。然后再进行dfs,这次要附加一个信息——从当前访问节点开始向父亲节点所能延伸到的最远距离d。每访问到一个点a的时候,S[a]=max(f[a],d[a])。还有一个问题要考虑的就是怎样维护d,假设我们已经有了d[i],现在我们要向子结点j递归,那么d[j]=max{d[i],max{f[k]+w[i,k]}(k为i的非j子结点)}+w[i,j]。这个方程朴素的复杂度是O(n^2)的,但是我们只需要求最大的元素,所以可以用平衡树来维护,直接用stl的map就可以搞定。代码如下:

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#define N 10009
using namespace std;
struct edge{
int v,w,p;
void init(int a,int b,int c){v=a,w=b,p=c;}
}E[N];
int n,ep;
int gra[N],f[N],S[N];
int addedge(int v,int w,int p){
E[++ep].init(v,w,p);
return ep;
}
int init_f(int rt){
for(int i=gra[rt];i;i=E[i].p)
f[rt]=max(f[rt],init_f(E[i].v)+E[i].w);
return f[rt];
}

void init_S(int rt,int pre){
S[rt]=max(f[rt],pre);
map<int,int> hsh;
map<int,int>::iterator it;
hsh[pre]++;
for(int i=gra[rt];i;i=E[i].p)
hsh[f[E[i].v]+E[i].w]++;
for(int i=gra[rt];i;i=E[i].p){
it=hsh.find(f[E[i].v]+E[i].w);
if(it->second==1) hsh.erase(it);
else it->second--;
init_S(E[i].v,hsh.rbegin()->first+E[i].w);
hsh[f[E[i].v]+E[i].w]++;
}
}

int main()
{
int x,y;
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
scanf("%d%d",&x,&y);
gra[x]=addedge(i,y,gra[x]);
}
init_f(1);
init_S(1,0);
for(int i=1;i<=n;i++) printf("%d\n",S[i]);
}


       给一棵树和一个起点s,然后给定一些点,求从s开始把所有的给定点都访问一遍的最小代价。状态为dp[n][2],dp[i][0]表示从i节点开始把其子树上的所有的给定点都访问一遍并回到i节点的最小代价,dp[i][1]表示从i节点开始把其子树上的所有的给定点都访问一遍并不用回到i节点的最小代价。假设我们从i节点开始访问他的子树中的给定点并不用返回i。那么必然是除了一棵以其某子结点为根的子树外,以其他的子结点为根的子树都是访问完了以后还要回到根节点,所以枚举一遍所有的子结点就可以算出dp[i][1]。复杂度为O(n)。

       这两题都类似,第二题是第一题的加强版,状态为dp[n][k],表示用k个机器人从n节点开始把其子树上的所有节点都访问完并不回到根节点的最小代价,为了表示方便,定义k=0的时候为用一个机器人访问完所有子结点并回到根节点的最小代价。k=0的时候很好算,那么怎么求dp[i][j]呢?假设i节点有k个子结点,那么dp[i][j]=min{k个节点中选若干个子节点用j个机器人访问并不返回的最小代价+剩下的子结点用一个机器人访问完并回到根节点的最小代价}(所有的机器人分配方案)。这个用背包DP的话就可以把复杂度降到O(n*k^2),其实这就是一个经典的多叉转二叉的模型。用的vector存边,所以有点慢,下面是第二题的代码:

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define N 10009
using namespace std;
struct edge{
int v,c;
edge(){}
edge(int v,int c):v(v),c(c){}
};
vector<edge> gra[N];
int n,s,m,dp[N][11],f[N][11];
void dfs(int r,int pr)
{
int i=0,p,c;
for(int i=0;i<gra[r].size();i++)
if(gra[r][i].v!=pr)
dfs(gra[r][i].v,r);
for(int l=0;l<gra[r].size();l++)
if((p=gra[r][l].v)!=pr)
{
c=gra[r][l].c;
i++;
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j]+2*c+dp[p][0];
for(int k=1;k<=j;k++)
f[i][j]=min(f[i][j],f[i-1][j-k]+k*c+dp[p][k]);
}
}
if(i)
for(int j=0;j<=m;j++)
dp[r][j]=f[i][j];
else
memset(dp[r],0,sizeof(dp[r]));
}
int main()
{
for(int i=1;i<=m;i++) f[0][i]=1000000000;
while(scanf("%d%d%d",&n,&s,&m)+1)
{
for(int i=1;i<=n;i++) gra[i].clear();
for(int i=1;i<n;i++)
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
gra[x].push_back(edge(y,w));
gra[y].push_back(edge(x,w));
}
dfs(s,0);
int ans=dp[s][0];
for(int i=1;i<=m;i++) ans=min(ans,dp[s][i]);
printf("%d\n",ans);
}
return 0;
}


       经典的多叉转二叉,方法和上面两题类似,也是用背包来求出最优组合,复杂度O(n*k^2)。

       这题思路一下就有了,DP求每个子树连到子树外的新边的数量,假设为f(n),f(n)=n点的度数+所有子节点p的f(p)-2*LCA为n的新边数。LCA复杂度O(n*logn),树形DP复杂度O(n)。但交了N次才过,先是用的vector存边,所以无限TLE,改过来后又无限WA,后来发现了几个纱布错误,改过来了后再交又RE了,然后发现边数组只开了N,双向边应该是2*N......这里改正后终于719ms AC了。

       后来翻discuzz,发现大家做法千奇百怪,最多人用的一种方法就是:初始所有的边权值为0,考虑每一条额外的边把两个顶点x和y接起来,就把树上从x到y的路径上的边的权值都+1,最后统计权值为0和为1的边的个数,个人感觉有点蛋疼。还有一位神牛提供了一种O(n)的做法,研究了一下感觉和我的思路是差不多的,不过他用一种很巧妙的方法避免了求LCA,按着这种思路写了一个,果然更快了一些,547ms AC。但是不知道那些1XXms是怎么做到的。下面是第二种思路的代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 100009
using namespace std;
struct edge{
int v,p;
}E[N*2];
struct state{
int T[5],n;
void add(int x){
if(!n){T[n++]=x;return;}
int i=0;
for(;i<n&&x>T[i];i++);
for(int j=n++;j>i;j--) T[j]=T[j-1];
T[i]=x;
if(n<5) return;
n=4;
for(i=2;i<n;i++)T[i]=T[i+1];
}
}dp[N];
int n,m,ep,id[N],R[N],time;
long long ans;
bool vis[N];
int gra[N];
int addedge(int v,int p){
E[++ep].v=v;
E[ep].p=p;
return ep;
}
int dfs(int rt){
vis[rt]=true;
id[rt]=R[rt]=++time;
for(int i=gra[rt];i;i=E[i].p)
if(!vis[E[i].v])
R[rt]=max(R[rt],dfs(E[i].v));
return R[rt];
}

int init_dp(int rt)
{
vis[rt]=true;
int p,t,ret=0;
for(int i=gra[rt];i;i=E[i].p)
if(!vis[p=E[i].v])
{
t=init_dp(p);
if(!t) ans+=m;
else if(t==1) ans++;
for(int i=0;i<dp[p].n;i++)
dp[rt].add(dp[p].T[i]);
}
for(int i=0;i<dp[rt].n;i++)
if(dp[rt].T[i]<id[rt]||dp[rt].T[i]>R[rt])
ret++;
return ret;
}

int main()
{
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
gra[x]=addedge(y,gra[x]);
gra[y]=addedge(x,gra[y]);
}
dfs(1);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
dp[x].add(id[y]);
dp[y].add(id[x]);
}
memset(vis,false,sizeof(vis));
init_dp(1);
printf("%lld\n",ans);
}


       以前做的一道题目,题意很简单,给你一颗树,求最小添加多少条边可以使每一个点都在且仅在一个环上。当时我还以为是个图论啥的,想了半天都没有思路,后来实在没办法只好找解题报告才把这题给过了。这是一道树形DP的好题,状态的设计和装移比较巧妙,具体看这里。

       dp[x][0]表示以x为根的树,每个顶点在一个环中的最少边数。
       dp[x][1]表示以x为根的树,除了根x以外,其余每个顶点在一个环中的最少边数。
       dp[x][2]表示以x为根的树,除了根x以及和根相连的一条链以外,其余每个顶点在一个环中的最少边数。

写起来感觉非常蛋疼,各种边界什么的,折腾了好久,AC代码如下:

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int n,dp[ 109 ][ 3 ],vis[ 109 ];
vector<int> gra[ 109 ];
int mmin( int a,int b ){
if( a==-1 ) return b;
if( b==-1 ) return a;
return min( a,b );
}
void gao( int a ){
int cnt=0,tot=0;
vis[ a ]=1;
for( int i=0;i<gra[ a ].size( );i++ )
if( !vis[ gra[ a ][ i ] ] ){
gao( gra[ a ][ i ] );
if( dp[ gra[ a ][ i ] ][ 0 ]==-1 ) cnt++;
tot+=dp[ gra[ a ][ i ] ][ 0 ];
}
if( !cnt ) dp[ a ][ 1 ]=tot;
if( cnt>2 ) return;
if( cnt<=1 ){
for( int i=0;i<gra[ a ].size( );i++ ){
int p=gra[ a ][ i ];
if( vis[ p ]!=1&&( !cnt||dp[ p ][ 0 ]==-1 ) ){
int temp=mmin( dp[ p ][ 1 ],dp[ p ][ 2 ] );
if( temp!=-1 ) temp+=tot-dp[ p ][ 0 ];
dp[ a ][ 2 ]=mmin( dp[ a ][ 2 ],temp );
temp=dp[ p ][ 2 ];
if( temp!=-1 ) temp+=tot-dp[ p ][ 0 ]+1;
dp[ a ][ 0 ]=mmin( dp[ a ][ 0 ],temp );
}
}
}
for( int i=0;i<gra[ a ].size( );i++ )
for( int j=0;j<gra[ a ].size( );j++ ){
int p1=gra[ a ][ i ],p2=gra[ a ][ j ];
if( i==j||vis[ p1 ]==1||vis[ p2 ]==1 ) continue;
int dd=cnt,t1=mmin( dp[ p1 ][ 1 ],dp[ p1 ][ 2 ] ),t2=mmin( dp[ p2 ][ 1 ],dp[ p2 ][ 2 ] );
if( t1==-1||t2==-1 ) continue;
if( dp[ p1 ][ 0 ]==-1 ) dd--;
if( dp[ p2 ][ 0 ]==-1 ) dd--;
if( dd ) continue;
int temp=tot-dp[ p1 ][ 0 ]-dp[ p2 ][ 0 ]+t1+t2+1;
dp[ a ][ 0 ]=mmin( dp[ a ][ 0 ],temp );
}
vis[ a ]=2;
}
int main( void ){
scanf( "%d",&n );
for( int i=1;i<n;i++ ){
int x,y;
scanf( "%d%d",&x,&y );
gra[ x ].push_back( y );
gra[ y ].push_back( x );
}
memset( dp,-1,sizeof( dp ) );
gao( 1 );
printf( "%d\n",dp[ 1 ][ 0 ] );
}



  评论这张
 
阅读(623)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017