树形动态规划总结

发布于 2018-12-06  748 次阅读

 

树形动规总结

树型动规的基本方式同普通的线性动态规划，但遍历的顺序是由高深度向低深度直至根节点，通常一个树型动规包括了状态、阶段、决策、状态转移方程，找到每个题目对应的动归要素，是一个题目的难点所在。

  1. 状态：程序求解到每个程度所储存的信息，通常我们需要在一开始找到适合题目的状态并进行定义。Tips：找状态可以通过确定变量，权衡变量的范围来寻找。
  2. 阶段：就是求解动态规划的顺序，每次求解的状态都必须运用之前已经求解过的作为辅助。
  3. 决策：选择最优解的过程，通常是求最大值，最小值等。
  4. 状态转移方程：思考出决策后，用状态转移方程将其表达出来。

 

关于求解顺序：由于树形动归的特殊性（几乎都是无向边），我们应该从叶子节点开始遍历，有三种方法：

  1. 先给树做一次BFS，然后将队列中的元素一一出队，就是树型动规的顺序。
  2. 找度为2的节点，记录，并且更新它的子节点的度数，重复这个拓扑排序操作，得到的也是树型动规的顺序。
  3. 用递归将树的后序遍历求出，即可将一棵树线性化

 

拓展：状态压缩

      当我们的某个状态过于繁琐，很难将其用一个维度表示出来，怎么办？

如山贼集团题目，设立分部的时候各个分部会互相影响，而且不同的分部之间影响的情况是不同的，不像我们通常的动归，所有的物品一视同仁。

      比如某结点选择1、2、3分部，会导致总资金损失，而选择1、4分部，总资金却会增加……

      观察分部的总数量，小于等于8，这个时候我们可以用到位运算的相关知识，将1~8分部的选择情况用一个int变量储存起来，从而起到表示状态的作用。

 

 

 

Ural 1039没有上司的晚会

背景

有个公司要举行一场晚会。

为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司

（上司的上司，上司的上司的上司……都可以邀请）。

题目

每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。

输入格式

第1行一个整数N（1<=N<=6000）表示公司的人数。

接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。

接下来每行两个整数L，K。表示第K个人是第L个人的上司。

输入以0 0结束。

输出格式

一个数，最大的气氛值和。

样例输入

7

1

1

1

1

1

1

1

1 3

2 3

6 4

7 4

4 5

3 5

0 0

样例输出

5

提交地址：

http://acm.timus.ru/submit.aspx?space=1&num=1039

首先定义状态：每个结点，然后我们发现在一个人在不参与聚会时，它的相邻子节点可以参加聚会，也可以不参加；一个人参与聚会时，它的相邻子节点一定不能参与聚会。我们加一个状态：参与或者不参与聚会。

dp[i][j]表示第i个人参与(j==1)或不参与(j==0)聚会时聚会所能达到的最大气氛值

#include
#include
#include
using namespace std;
const int MAX=8000;
int w[MAX],f[MAX][2],l,k,rt;
int que[MAX],top,rear,father[MAX];
int first[MAX],nxt[MAX],go[MAX],arcnum;
void addarc(int a,int b){
    nxt[++arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum]=b;
}

int main(){
//   freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
        
    while(scanf("%d%d",&l,&k)!=EOF&&l!=0&&k!=0){
        father[l]=k;
        addarc(k,l);
    }
    
/*   for(int i=1;i<=n;i++){
        printf("%d ",i);
        for(int p=first[i];p!=0;p=nxt[p]){
            int j=go[p];
            printf("%d ",j);
        }
        printf("\n");
    }printf("\n");*/
    for(int i=1;i<=n;i++)
        if(!father[i]){
            rt=i; break;
        }
    que[rear++]=rt;
    do{
        for(int p=first[que[top++]];p!=0;p=nxt[p])
            que[rear++]=go[p];
    }while(top!=rear);
    
    for(int k=top-1;k>=0;k--){
        int i=que[k];
        if(first[i]==0){
            f[i][0]=0;
            f[i][1]=w[i];
        }else{
            int sum,j;
            sum=0;
            for(int p=first[i];p!=0;p=nxt[p]){
                j=go[p];
                sum+=max(f[j][0],f[j][1]);
            }
            f[i][0]=sum;
            sum=0;
            for(int p=first[i];p!=0;p=nxt[p]){
                j=go[p];
                sum+=f[j][0];
            }
            f[i][1]=sum+w[i];
        }
    }
    printf("%d",max(f[rt][0],f[rt][1]));
    
    
/*   printf("\n");
    for(int i=1;i<=n;i++){
        printf("%d %d\n",f[i][0],f[i][1]);
    }*/
    
    
    return 0;
}

POJ 1985 Cow Marathon

题目大意

求一棵树的最长路径

输入：

第一行：n,m (2 <= N <= 40,000,1 <= M< 40,000)，表示有n个节点，m条边

接下来m行：

每行四个量：a b w c，表示a与b之间有一条权值为w的路径，将c忽略掉

输出：

最长路径长度

模版题 但是WA了，就不给代码了。。。。

Ural 1018 二*苹果树

题目

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）
这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树
2   5
\ /
3   4
\ /
1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。

输入格式

第1行2个数，N和Q(1<=Q<=N,1<N<=100)。
N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。
每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过30000个。

输出格式

一个数，最多能留住的苹果的数量。

样例输入

5 2
1 3 1
1 4 10
2 3 20
3 5 20

样例输出

21

状态：结点、树所保留的树枝数量。

f[i][j]表示在第i个结点以下的子树保留j个树枝所能保留的最大苹果数

分配树枝需要枚举分配给整个子树的树枝数、再枚举分给左右子树的树枝各有多少，注意这里分给左右子树树枝的同时会损失掉两根树枝

 

#include
#include
#include
using namespace std;
const int MAX=1000;
int first[MAX],nxt[MAX],go[MAX],w[MAX][MAX],arcnum;
int f[MAX][MAX],father[MAX],lch[MAX],rch[MAX],vis[MAX];
int que[MAX],top,rear;
void addarc(int a,int b,int c){
    nxt[++arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum]=b;
    w[a][b]=c;
}
int main(){
//   freopen("in.txt","r",stdin);
    int n,q,a,b,c;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n-1;i++){
        scanf("%d%d%d",&a,&b,&c);
        addarc(a,b,c);
        addarc(b,a,c);
    }
    que[rear++]=1; vis[1]=1;
    do{
        int u=que[top++],v;
        for(int p=first[u];p!=0;p=nxt[p]){
            v=go[p];
            if(vis[v]) continue;
            if(!lch[u]) lch[u]=v;
            else rch[u]=v;
            que[rear++]=v; vis[v]=1;
        }
    }while(top!=rear);
    
    for(int k=top-1;k>=0;k--){
        int i=que[k];
        if(!lch[i]) continue;
        for(int j=1;j<=q;j++){//分配j个树枝 
            f[i][j]=max(f[i][j],max(f[lch[i]][j-1]+w[i][lch[i]],f[rch[i]][j-1]+w[i][rch[i]]));//单独分配 
            for(int j0=1;j0//两个都分配 
                int lw=f[lch[i]][j0-1]+w[i][lch[i]];
                int rw=f[rch[i]][j-j0-1]+w[i][rch[i]];
                f[i][j]=max(f[i][j],lw+rw);
            }
        }
    }
    printf("%d",f[1][q]);
    
    return 0;
}