树形动态规划(信息学竞赛)

树状动规1333:VIJOS-P1180选课想要选修某个课程，那么它的先修课必须要被选择。多叉树转二叉树动归。首先大家先了解多叉树转二叉树。原则：二叉树的结点x的左儿子为x的儿子，右儿子是x的兄弟。即左儿子，右兄弟原则。1333:选课（多叉树转二叉树）具体实现方法：使用数组模拟二叉树L[x]:表示X的左儿子是谁!初值-1R[x]:表示X的右儿子是谁！也就是X的兄弟，初值-1last[x]:表示原树中x的当前一个子节点son1现在的位置，假如x的另外一个儿子son2,要插入到二叉树中那么根据左儿子右兄弟的原则，既然son2跟son1为兄弟，那么就放到son1所在位置的右子树即可！代码：voidbuild(intx,inty)//y的父亲结点为x{if(L[x]==-1) L[x]

=

y;else R[

last[x]

]

=

y;last[x]=y;}1333:VIJOS-P1180选课状态F(x,y)：表示节点x取y门课得最高学分方程F(x,y)=max{F(R[x],k),F(L[x],k-1)+a[x]+F(R[x],y-k)}k=0,1,..yF(L[x],k-1)+a[x]:表示左孩子选了k-1门课及包括课程x,共k门课的最大学分。F(R[x],y-k)

表示右孩子只能选y-k门课的最大得分。分析出来了这么多，代码如何写才是关键，否则都是空中楼阁。我们引入记忆化搜索的思想，即每深搜一步，把搜做到的结果保存起来，当下次搜索到同样的位置时，直接使用！记忆化搜索经典题目：1911滑雪&&1257Functionintwork(intpos,intk){if(pos<0||k<=0)return0;

//递归退出条件if(f[pos][k]!=-1)returnf[pos][k];

//如果这个值以前被计算过，直接返回这个值f[pos][k]=work(r[pos],k);

//左子树不选任何一个for(inti=0;i<=k-1;i++)f[pos][k]=max(f[pos][k],

work(l[pos],i)+work(r[pos],k-i-1)+s[pos]);

//动规过程returnf[pos][k];}2140:通向自由的钥匙通向自由的钥匙被放n个房间里，这n个房间由n-1条走廊连接。注意：这就是一棵树。本题的动规的过程与上一题选课是一样的唯一不同的是题目给出树的根为1，还有树的联通性。建二叉树树的过程是需要大家仔细思考的。2140:通向自由的钥匙voidbuild(intx){for(inti=1;i<=n;i++)if(d[x][i]){d[x][i]=d[i][x]=0;if(

ls[x]==-1)

ls[x]=i;elsers[

last[x]

]=i;last[x]=i;build(i);}}1273:加分二叉树每一个结点有一个权值，给定的序列是中序遍历的点权序列。状态f[i][j]表示从i到j的中序序列组成的二叉树最大加分值。方程f[i][j]=max{f[i][k-1]*f[k+1][j]+f[k][k]}i<=k<=jf[i][k-1]和f[k+1][j]直接拿过来用肯能不会求出最大的f[i][j],所以要引入记忆化的思想，递归的求出这两个的值。1273:加分二叉树longlongwork(intx,inty){

if(x>y)returnf[x][y]=1;if(f[x][y]!=-1)returnf[x][y];for(intk=0;k<=y-x;k++)if(f[x][y]<f[x+k][x+k]+work(x,x+k-1)*work(x+k+1,y)){f[x][y]=f[x+k][x+k]+work(x,x+k-1)*work(x+k+1,y);root[x][y]=x+k; //记录x到y区间的根，以便最后递归输出先根遍历。}returnf[x][y];}POJ2342Anniversaryparty题意：一个人不同他的直属上司一起参加舞会，问参会人员的权值和的最大值。显然每个人只有两种状态参加或者不参加状态f[i][0]表示第i个人不参加，f[i][1]表示此人参加，所的得到的子树的最大值。f[i][1]+=f[j][0]; j是其下属的标号f[i][0]+=max{f[j][1],f[j][0]}本题使用链式前向星存边，找出根rootans=max{f[root][0],f[root][1]};POJ2342Anniversarypartyvoidwork(intx){

f[x][0]=0

,

f[x][1]=a[x];

//初始化 for(inty,i=head[x];i;i=next[i]) { y=to[i]; //y为x的子节点 work(y); //先处理完y才能动规x f[x][0]+=max(f[y][0],f[y][1]); f[x][1]+=f[y][0]; }}POJ3342PartyatHali-Bula基本题意与2342相同，需要特别判断与会名单是否唯一！思考判定方法？是否有特例！动规伴随着深搜，只需要考虑深搜时候的局部情况即可判定全局情况。即if(f[x][0]==f[x][1]&&f[y][1]==f[y][0])flag=0;思考当n==2时，只能一个人与会，名单不确定。但是使用上面的判断就不行了，需要特判一下即可。POJ2486AppleTreeN叉苹果树，结点上有苹果，问一共走k步，所能吃到的苹果的最大值。其中从A->B算一步，返回B->A再算一步。状态f[0][i][j]表示从i点走j步再回到i的最大值状态f[1][i][j]表示从i点走j步不回到i的最大值f[0][x][j+2]=max{f[0][x][j+2],f[0][y][k]+f[0][x][j-k]}f[1][x][j+2]=max{f[1][x][j+2],f[0][y][k]+f[1][x][j-k]}f[1][x][j+1]=max{f[1][x][j+1],f[1][y][k]+f[0][x][j-k]}POJ2486AppleTreevoiddfs(intx){

v[x]=1;

for(inti=0;i<=step;i++)f[1][x][i]=f[0][x][i]=a[x];

ints=t[x].size();

for(inty,i=0;i<s;i++)

{

y=t[x][i];

if(!v[y])

{ dfs(y); for(intj=step;j>=0;j--)

for(intk=0;k<=j;k++)

{

f[0][x][j+2]=max(f[0][x][j+2],f[0][y][k]+f[0][x][j-k]);

f[1][x][j+2]=max(f[1][x][j+2],f[0][y][k]+f[1][x][j-k]);

f[1][x][j+1]=max(f[1][x][j+1],f[1][y][k]+f[0][x][j-k]);

}

}

}}POJ3659CellPhoneNetwork题意：给出一棵树，树的每个节点都可以放信号塔，放信号塔的节点可以覆盖到它周围的节点，问选择最少的建信号塔的方案，使得树的所有节点都被覆盖。这样的问题叫做：最小支配集问题，使用树形动归来处理。考虑每个结点只有两种状态，放或者不放信号塔。其中如果这个点不放信号塔，并且还需要被覆盖，又有两种情况：一是其父亲结点放信号塔，二是其子节点中有一个放了信号塔。总结起来每个结点有三种情况：f[x][0]:x点的父亲结点放塔，以x为根的子树最少信号塔数f[x][1]:x点的子节点放塔，以x为根的子树的最少信号塔数f[x][2]:x点本身放信号塔，以x为根的子树最少信号塔数POJ3659CellPhoneNetwork那么动态方程为：设y为x的子结点f[x][0]+=min{f[y][1],f[y][2]}f[x][2]+=min{f[y][0],f[y][2]}f[x][1]的情况比较复杂，需要单独讨论了。x的子节点y中是否存在y的自己覆盖小于y的子节点z的覆盖，如果存在(f[y][2]<f[y][1]),那么这个y的分支就一定会被选中，进而辐射到y的根节点x。此时f[x][1]=f[x][0];如果上述情况没有出现的话，只能选择一个最优的y，使得y点放信号塔，来辐射到x。令temp=f[y][2]-f[y][1];那么f[x][1]=f[x][0]+temp;至此，动态转移方程就已经写完了，虽然有些复杂，但是对于我们深入理解动态规划有很深的影响。POJ3659CellPhoneNetwork结点的初值：f[x][0]=0;f[x][1]=0;f[x][2]=1;如果是叶子结点呢？if（叶子）f[x][1]=1<<30;最后的ans呢？ans=min（f[root][1],f[root][2]）poj3398PerfectService同样是最小支配集问题。我们使用另类的贪心方法来解决。1、深搜遍历，把深搜的顺序记录下来。其实深搜的顺序就是先根遍历的顺。2、根据先跟遍历的顺序逆向处理，也就是相当于回溯的过程。3、如果一个结点x的覆盖状态mark[x]==0,并且如果其根fa[x]的是否为server的状态为0，即set[fa[x]]==0,那么ans++，set[fa[x]]=1;4、不管set[fa[x]]是否为0，都要标记x,fa[x],fa[fa[x]]的状态为覆盖。思考为什么？poj3398PerfectServicevoiddfs(intx){ deep[++num]=x; for(inty,i=head[x];i;i=next[i]){ y=to[i]; if(!v[y]){ v[y]=1