树形动态规划-白红宇

树形动态规划

阅读量：4153 次

发布时间：2019-05-25

本文共 3768 字，大约阅读时间需要 12 分钟。

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

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

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 
   
    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
   
    #include
    
     #include
     
      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;}