hiho 9,12,13,15,17

#开始了一周一次的hiho题解.

这周题解有:

0) hiho 9, 简单dp.常见铺砖dp

1) hiho 12,分组背包.

2) hiho 13,15,17, 最近公共祖先问题. LCA

##0.hiho 9

题目9 代码9

题意:给定n*m的矩形,使用1*2或者2*1的木棍,填充求种数.

题解: dp[i][j]表示第i层,状态为j的种数.

A.每一种状态都是由上一层状态横着放,或者不横着放决定.

B.dfs(status,position)

C.如果上一层是0的块,一定要用1*2的木块填充,因此上一层是0的状态,这一层一定是1

    dfs(~status&((1<<m)-1),position)

##1.hiho 12 题目12 代码12

题意:给出一个树,选出跟根节点相连的最多M个节点,使权值最大.

题解:对于每一个节点,都相当于是个背包,最多可以选M个节点,对于当前节点的 每一个子树,都可以看成是一个分组,分组中有0到M个选择,每个选择都是对应着子树 的选择x个的最大权值.当然这一个分组最多只能选择一个.

int sz = e[x].size();
for(int i=0;i<sz;i++){
    for(int j=M;j>=2;j--){
        for(int k=0;k<j;k++)
            f[x][j]=max( f[x][j],f[ x ][j-k]+f[ e[x][i] ][k]);
    }
}

##2.hiho 13 15 17 题目13 代码13 题目15 代码15 题目17 代码17

题意:都是求最近公共祖先

题解:使用二分法求最近公共祖先.1)预处理出深度和2^k的父亲节点.2)求的时候首先将a,b统一到同一高度.3)从MAX_LOG_K开始尝试走一直到0, 两个节点的父亲节点,如果不相同,则同时网上走2^k,4)返回两个节点的父亲节点