精华内容
参与话题
问答
  • 树形动态规划

    千次阅读 2012-07-02 23:39:54
    树形动态规划的框架可以这样写: Proceduredfs(v);  var i:longint; Begin  vis[v]:=ture;  for i:=1 to n do  if father[i]=v then// 一般树形动态规划的操作是从叶子节点向根节点推导...

    树形动态规划的框架可以这样写:

    Proceduredfs(v);

      var i:longint;

    Begin

        vis[v]:=ture;

        for i:=1 to n do

           if father[i]=v then// 一般树形动态规划的操作是从叶子节点向根节点推导,所以必须要确定i时v的孩子

                   begin

                       if not vis[i]then  dfs(i);//如果孩子节点i已经被计算过就不需要再次计算,这里就体现了动态规划的思想

                        dp[v]            fun(dp[i])//这里的分支递归又体现了树的递归操作思想

                   end;

    End;



    l在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程a是课程b的先修课即只有学完了课程a,才能学习课程b)。一个学生要从这些课程里选择M门课程学习,问他能获得的最大学分是多少?
    l输入:
    l第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=200)
    l接下来的N行,第I+1行包含两个整数ki和si,ki表示第I门课的直接先修课,si表示第I门课的学分。若ki=0表示没有直接先修课(1<=ki<=N, 1<=si<=20)。
    l输出:
    只有一行,选M门课程的最大得分


    我们用函数f(i,j)表示以第i个节点为父节点,取j个子节点的最佳代价,则:

    l可是如此规划,其效率与搜索毫无差别,虽然我们可以再次用动态规划来使它的复杂度变为平方级,但显得过于麻烦。

    l转变为二叉树。如果两节点a,b同为兄弟,则将b设为a的右节点;如果节点b是节点a的儿子,则将节点b设为节点a的左节点。树改造完成后如图3。
    l我们用函数f(I,j)表示以第i个节点为父节点,取j个子节点的最佳代价,这和前一个函数表示的意义是一致的,但方程有了很大的改变:







    1039. Anniversary party

    Time Limit: 1.0 second
    Memory Limit: 16 MB

    Background

    The president of the Ural State University is going to make an 80'th Anniversary party. The university has a hierarchical structure of employees; that is, the supervisor relation forms a tree rooted at the president. Employees are numbered by integer numbers in a range from 1 to N, The personnel office has ranked each employee with a conviviality rating. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend.

    Problem

    Your task is to make up a guest list with the maximal conviviality rating of the guests.

    Input

    The first line of the input contains a number N. 1 ≤ N ≤ 6000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from –128 to 127. After that the supervisor relation tree goes. Each line of the tree specification has the form
    <L> <K>
    which means that the K-th employee is an immediate supervisor of L-th employee. Input is ended with the line
    0 0

    Output

    The output should contain the maximal total rating of the guests.

    Sample

    input output
    7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
    5


    a[i].in=∑a[i.son].out

    a[i].out=∑max{a[i.son].in, a[i.son].out}

    in 表示q请 i  ,out 表示b不请 i 。


    下面说下左儿子右兄弟x新节点的c插入方法:

    1。这是一棵二叉树(不大相就是)

    2。先帮他认好父亲和兄弟



    3。让他爸认识他,并遗弃他的二哥   (为逃过罚款,户口上只能有一个儿子)

     

    #include <iostream>
    using namespace std;
    struct node {
     int boss,son,brother;
            int in,out;
     void init()
     {
      boss = brother = son = in = out = 0 ;
     }
     int max()
        {
            return in > out ? in : out ;
        }
    } a[6002];
    void treedp(int father){                      
     int son = a[father].son;
     while (son) {
      treedp(son);
      a[father].in+=a[son].out;
      a[father].out+=a[son].max();
      son=a[son].brother;
     }
     
    }
    int main(){
     int i,l,k,n;
     
     while(cin >> n){
     for (i=1; i<=n; i++) {
      a[i].init();
         cin >> a[i].in;
     }
        while (cin >>l >>k && l+k) {               //边读入建二叉树
      a[l].boss = k;
      a[l].brother = a[k].son; 
      a[k].son = l;
     } 
        for (i=1;i<=n;i++)
            if (a[i].boss==0) {
        treedp(i);
              cout << a[i].max() << endl;
        break;
      }
    }
    }


    也可以不转换二叉树


    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int MAXN=6003;
    int a[MAXN];
    int father[MAXN];
    int f[MAXN][2];
    int n;
    
    void TreeDP(int i)
    {
        f[i][1]=a[i];
        for(int j=1;j<=n;j++)
        {
            if(father[j]==i)
            {
                TreeDP(j);
                f[i][0]+=max(f[j][0],f[j][1]);
                f[i][1]+=f[j][0];
            }
        }
    }
    
    int main()
    {
    
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
        }
        int x,s;
        memset(father,0,sizeof(father));
        memset(f,0,sizeof(f));
        while(scanf("%d %d",&x,&s),x&&s)
        {
            father[x]=s;
        }
    
        for(int i=1;i<=n;i++)
        {
            if(father[i]==0)
            {
                TreeDP(i);
                printf("%d\n",max(f[i][0],f[i][1]));
                break;
            }
        }
    
    
        return 0;
    }

    http://hi.baidu.com/keynoheart/blog/item/7c820ed0f9a2423e06088b64.html

    http://www.cppblog.com/cxiaojia/archive/2011/12/04/ural1039.html







    展开全文
  • 暂时看的一个比较好地讲解树形DP的课件,对初步了解树形DP有帮助
  • 树形DP详细讲解
  • 顾名思义,树型动态规划就是在“”的数据结构上的动态规划,平时做的动态规划都是线性的或者是建立在图上的,线性的动态规划有二种方向即向前和向后,相应的线性的动态规划有二种方法即顺推与逆推,而树型动态规划...

    顾名思义,树型动态规划就是在“树”的数据结构上的动态规划,平时做的动态规划都是线性的或者是建立在图上的,线性的动态规划有二种方向即向前和向后,相应的线性的动态规划有二种方法即顺推与逆推,而树型动态规划是建立在树上的,所以也相应的有二个方向:

    • 根—>叶:此类动态规划在实际的问题中运用较少;
    • 叶—>根:即根的子节点传递有用的信息给根,完后根得出最优解的过程。

    例:PARTY AT HALI-BULA

    【问题描述】
    n个人形成一个关系树,每个节点代表一个人,节点的父节点表示这个人的唯一的直接上司,只有根没有上司。要求选取一部分人出来,使得每2个人之间不能有直接的上下级的关系,求最多能选多少个人出来,并且求出获得最大人数的选人方案是否唯一。

    【分析】

    这是一个经典的树型动态规划。简单的染色统计是不正确的,人之间的关系形成树型结构。

    DP, 用dp[i][0]表示不选择i点时,i点及其子树能选出的最多人数,dp[i][1]表示选择i点时,i点及其子树的最多人数。状态转移方程:
    对于叶子节点,dp[k][0] = 0, dp[k][1] = 1
    对于非叶子节点i,dp[i][0] = ∑max(dp[j][0], dp[j][1]) (j是i的儿子),dp[i][1] = 1 + ∑dp[j][0] (j是i的儿子)
    最多人数即为max(dp[0][0], dp[0][1])。
    如何判断最优解是否唯一?新加一个状态dup[i][j],表示相应的dp[i][j]是否是唯一方案。
    对于叶子结点, dup[k][0] = dup[k][1] = 1。对于非叶子结点,对于i的任一儿子j,若(dp[j][0] > dp[j][1] 且 dup[j][0] == 0) 或 (dp[j][0] < dp[j][1] 且 dup[j][1] == 0) 或 (dp[j][0] == dp[j][1]),则dup[i][0] = 0。对于i的任一儿子j有dup[j][0] = 0, 则dup[i][1] = 0。

    例:STRATEGIC GAME

    【问题描述】
    一城堡的所有的道路形成一个n个节点的树,如果在一个节点上放上一个士兵,那么和这个节点相连的边就会被看守住,问把所有边看守住最少需要放多少士兵。

    【分析】

    dproot[ i ]表示以i为根的子树,在i上放置一个士兵,看守住整个子树需要多少士兵。
    all[ i ]表示看守住整个以i为根的子树需要多少士兵。
    状态转移方程:
         叶子节点:dproot[k] =1; all[k] = 0;
         非叶子节点:dproot[i] = 1 + ∑all[j](j是i的儿子);
         all[i] = min( dproot[i],  ∑dproot[j](j是i的儿子) )。

    例:中序转前序

    【输入格式】
    第1行:一个整数n(n<30),为节点个数。
    第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。

    【输出格式】
    第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。
    第2行:n个用空格隔开的整数,为该树的前序遍历。

    【输入样例】
    5
    5 7 1 2 10

    【输出样例】
    145
    3 1 2 4 5

    【分析】

    本题适合用动态规划来解。如果用数组value[i,j]表示从节点i到节点j所组成的二叉树的最大加分,则动态方程可以表示如下:
    value[i,j]=max{value[i,i]+value[i+1,j],
                  value[k,k]+value[i,k]*value[k+1,j] | i<k<j,
                  value[i,j-1] + value[j,j] };
    第一项 为 左子树为空, 根为i,右子树[i+1,j]。
    第二项 为 左子树为i,根为i+1,右子树为[i+2,j].
    必要条件:子树之间不可以相互干扰,如果本来是相互干扰的,那么我们必须添加变量使得他们不相互干扰。
    树形动态规划通常从叶节点(边界)开始逐步向上一层的节点(即父节点)进行状态方程的转移,直到根节点。

    例:NOIP2003-加分二叉树

    【问题描述】
    设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:
    subtree的左子树的加分×subtree的右子树的加分+subtree的根的分数,若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。
    试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出:(1)tree的最高加分,(2)tree的前序遍历。

    【输入格式】
    第1行:一个整数n(n<30),为节点个数。
    第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。
    【输出格式】
    第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。
    第2行:n个用空格隔开的整数,为该树的前序遍历。
    【输入样例】(binary.in)
    5
    5 7 1 2 10
    【输出样例】(binary.out)
    145
    3 1 2 4 5

    【问题分析】

    本题考查二叉树的遍历和动态规划算法。难点在于要记录当前最大加分二叉树的根节点。疑点是最大加分二叉树的前序遍历序列可能不唯一。很显然本题适合用动态规划来解。如果用数组f[i,j]表示从节点i到节点j所组成的二叉树的最大加分,则动态方程可以表示如下:
    f[i,j]=max {f[i,i]+f[i+1,j],f[k,k]+f[i,k–1]*f[k+1,j],f[j,j]+f[i,j-1]}
    题目还需输出最大加分树的前序遍历序列,因此需在计算过程中记下从节点i到节点j所组成的最大加分二叉树的根节点,用数组s[i,j]表示。

    例:URAL1018-苹果二叉树
    【问题描述】
    有一棵苹果树,如果树枝有分叉,一定是分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]:=max{f[left[i],k-1]+f[right[i],j–k]}+a[i],0<k<=j

    Function treedp(x,y:longint):longint;
    VarI,j,k:longint;
    Begin
     J:=0;
     For I:=0 to y do
     begin
      k:=treedp(b[x].left,I-1)+treedp(b[x].right,y-I)+a[x];
      if k>j then j:=k;
     end;
     treedp:=j;
    End;

    例:CTSC1997-选课

    【问题描述】
    在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程a是课程b的先修课即只有学完了课程a,才能学习课程b)。一个学生要从这些课程里选择M门课程学习,问他能获得的最大学分是多少?

    【输入格式】
    第一行有两个整数N,M用空格隔开(1<=N<=200,1<=M<=150)
    接下来的N行,第i+1行包含两个整数ki和si, ki表示第i门课的直接先修课,si表示第i门课的学分。若ki=0表示没有直接先修课(1<=ki<=N, 1<=si<=20)。
    【输出格式】
    只有一行,选M门课程的最大得分。
    【输入样例】
    7 4
    2 2
    0 1
    0 4
    2 1
    7 1
    7 6
    2 2
    【输出样例】
    13

    【问题分析】

    这题比苹果树多了一个步骤就是把一棵普通树转化为二叉树。读入数据时把二叉树建好:第一个孩子作为父节点的左子树,其它孩子作为第一个孩子的右子树。F(x,y):表示节点x取y门课得最高学分,则:
    F(x,y)=max(f(x.l,k-1)+x.v+f(x.r,y-k))k=1,2,..y
    f(x.l,k-1)+x.v(课程x的学分):表示选了课程x,左孩子选k-1门课,共k门课;f (x.r,y-k):表示右孩子只能选y-k门课。节点0表示根节点,1~n是n门可选课程的节点。

    例:苹果多叉树

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

    【问题分析】

    f[i,j]:=max{f[left[i],k-1]+f[right[i],j–k]+a[k],f[right[i],j]},0<k<=j

    例:URAL1039-没有上司的晚会

    【问题描述】
    有个公司要举行一场晚会。
    为了能玩得开心,公司领导决定:如果邀请了某个人,那么一定不会邀请他的上司(上司的上司,上司的上司的上司……都可以邀请)。
    每个参加晚会的人都能为晚会增添一些气氛,求一个邀请方案,使气氛值的和最大。

    【输入格式】
    第1行一个整数N(1<=N<=6000)表示公司的人数。
    接下来N行,每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
    接下来每行两个整数L,K。表示第K个人是第L个人的上司。
    输入以0 0结束。
    【输出格式】
    一个数,最大的气氛值和。

    【问题分析】

    这是树型动态规划的一种分类,每个结点都有二种状态既选与不选。f[i,1]表示邀请i的最大值,f[i,2]表示不邀请i的最大值,f[i,1]=sigma(f[i.sons,2])+a[i],f[i,2]= sigma{max(f[i.sons,1], f[i.sons,2])}。

    F[i,1]=max{f[left[i],0]+f[right[i],0],f[left[i],0]+f[right[i],1]},F[I,0]=max{f[left[i],1]+f[right[i],0],f[left[i],0]+f[right[i],0]}

     

    展开全文
  • 动态规划之树形动态规划

    千次阅读 2012-07-09 17:47:30
    二叉苹果  题目  有一棵苹果,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的结点)  这棵共有N个结点(叶子点或者树枝分叉点),编号为1-N,树根编号一定是1。  我们用一根树枝两端连接的...
    二叉苹果树 

    题目 
    有一棵苹果树,如果树枝有分叉,一定是分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][m]表示第i个节点下,共保留m个树枝的最大苹果数目。

    ch[i,L]表示i树左边的枝条集合, ch[i,R]表示i树右边的枝条集合

    f[ch[i,L],n]表示在i树左边的枝条集合中选取n个枝条的最大苹果数目

    f[ch[i,R],n]表示在i树右边的枝条集合中选取n个枝条的最大苹果数目

    方程:f[i][m]=max{ f[ch[i,L],n]+f[ch[i,R],m-n]]} (0<=n<=m) 其中L,R为i的左右子树 

    公式太抽象,举个例子

    对于如下苹果树


    有7个节点a,b,c,d,e,f,g; 有6条边,边的权重分别为5,24,20,30,21,27

    求f[a][4],即只保留4个枝条,最多留下多少苹果?

    根据公式,f[a][4] = max

    {

    f[ch[a,L],3]+f[ch[a,R],1],

    f[ch[a,L],2]+f[ch[a,R],2],

    f[ch[a,L],1]+f[ch[a,R],3]

    }

    其中f[ch[a,L],3]=f[b,2] + 5 (枝条ab的权重);

    所以

    f[a][4] = max

    {

    5+f[b][2]+24,

    5+f[b][1]+24+f[c][1],

    5+24+f[c][2]

    }

    f[b][2]=50,f[b][1]=30,f[c][1]=27,f[c][2]=48

    f[a][4] =f[ch[a,L],2] + f[ch[a,R],2]=

    5+f[b][1]+24+f[c][1]=86;


    题目2:看守道路

    一个城堡的所有的道路形成一个n个节点的树,如果在一个节点上放上一个士兵,那么和这个节点相连的边就会被看守住,问把所有边看守住最少需要放多少士兵?

    这个题目,是典型的树形动态规划

    求解:
    dproot[i]表示以i为根的子树,在i上放置一个士兵,看守住整个子树需要多少士兵。
    all[i]表示看守住整个以i为根的子树需要多少士兵。(不一定要在i上,放置士兵)

    状态转移方程:
    叶子节点:dproot[k]=1; all[k]=0;

    all[k]=0表示要看守住含有叶子节点道路,一定可以不用在叶子节点放置守卫
    非叶子节点:
    dproot[i]=1+∑all[j](j是i的儿子);
    all[i]=min(dproot[i],∑dproot[j](j是i的儿子));

    这个题目还是比较简单的,如果把题目中树改为看守一个n个节点的图呢?

    展开全文
  • 树形:http://www.cnblogs.com/gq-ouyang/archive/2013/02/26/2933431.html 区间型:http://blog.csdn.net/xuzengqiang/article/details/7862992

    树形:http://www.cnblogs.com/gq-ouyang/archive/2013/02/26/2933431.html

    区间型:http://blog.csdn.net/xuzengqiang/article/details/7862992

                   http://www.cnblogs.com/IThaitian/archive/2012/07/12/2588704.html

    展开全文
  • 树形动态规划,是指当动态规划的各阶段形成一棵树,利用各阶段之间的关系(动态转移方程),从叶节点(边界)开始逐步向上一层的节点(即父节点)进行动态规划,直到动规到根节点,(即原问题),求
  • 树形动态规划题集

    2020-01-10 13:00:54
    1575:【例 1】二叉苹果 问题描述 有一棵二叉苹果,如果数字有分叉,一定是分两叉,即没有只有一个儿子的节点。这棵共 N 个节点,标号 1 至 N,树根编号一定为 1。 我们用一根树枝两端连接的节点编号描述一根...
  • 选课 树形动态规划

    2016-05-08 11:01:25
    题目大意 在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。...因为是多叉,所以要转换成
  • 在此基础上,求保留多少个点使得其仍然满足的性质且权值总和最大。 分析  具体方法见:http://blog.csdn.net/a_loud_name/article/details/51326123 代码 var f:array[0..200,0.....
  • 树形动态规划总结

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

    2015-10-23 15:02:00
    1.OJ1278战略游戏  f[u][0]代表以u为根的子树,u不放时,最少放置节点数。  f[u][1]代表以u为根的子树,u放时,最少放置节点数。  f[u][0]=Σf[son][1]。 ... f[u][1]=Σmin(f[son][1],f[son][0])。...

空空如也

1 2 3 4 5 ... 20
收藏数 1,041
精华内容 416
关键字:

树形动态规划