hdu--1520--树形dp<写起来就是深搜啊>-<滚动数组优化>

我肯定还没怎么理解树形dp啊...为什么写下去就感觉是多了个状态转移方程的深搜呢？或者因为树形dp是依托在树这个数据结构上所进行的所以是这样的？

这题被很多人当做树形dp的入门题的确....

如果 u 是 v 的前驱即父母那么

dp[u][0] += max( dp[v][1] , dp[v][0] ) 0表示u不包括在内 1在内

dp[u[[1] += dp[v][0]

不太难写还好这个

主要是每个树形dp都要找出根结点

因为数据很宽松我直接用了vector来写

 1 #include <iostream>
 2 #include <cstring>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int size = 6010;
 8 vector<int>ve[size];
 9 int val[size];
10 int dp[size][2];
11 int in[size];
12 
13 void dfs( int u )
14 {
15     int Size , v;
16     Size = ve[u].size();
17     dp[u][1] = val[u];
18     for( int i = 0 ; i<Size ; i++ )
19     {
20         v = ve[u][i];
21         dfs(v);
22         dp[u][0] += max( dp[v][0] , dp[v][1] );
23         dp[u][1] += dp[v][0];
24     }
25 }
26 
27 int main()
28 {
29     cin.sync_with_stdio(false);
30     int n , x , y , z;
31     while( cin >> n )
32     {
33         memset( dp , 0 , sizeof(dp) );
34         memset( in , 0 , sizeof(in) );
35         for( int i = 1 ; i<=n ; i++ )
36         {
37             cin >> val[i];
38             ve[i].clear();
39         }
40         while(1)
41         {
42             cin >> x >> y;
43             ve[y].push_back(x);
44             in[x] ++;
45             if( !x && !y )
46                 break;
47         }
48         for( int i =1 ; i<=n ; i++ )
49         {
50             if( !in[i] )
51             {
52                 z = i;
53                 break;
54             }
55         }    
56         dfs(z);
57         cout << max( dp[z][0] , dp[z][1] ) << endl;
58     }
59     return 0;
60 }

View Code

看了discuss里面一个人的滚动数组写法很有感触

因为这边每个结点只需要利用与它直接相连的后驱结点的信息所以我们可以用滚动数组优化

要注意的是arr数组必须写在函数内使它变成局部变量

 1 #include <iostream>
 2 #include <cstring>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int size = 6010;
 8 vector<int>ve[size];
 9 int val[size];
10 int dp[2] = {0,0};
11 int in[size];
12 
13 void dfs( int u )
14 {
15     int arr[2] = {0,0};
16     int Size = ve[u].size();
17     for( int i = 0 ; i<Size ; i++ )
18     {
19         dfs( ve[u][i] );
20         arr[0] += max( dp[0] , dp[1] );
21         arr[1] += dp[0];
22     }
23     dp[0] = arr[0];
24     dp[1] = arr[1] + val[u];
25 }
26 
27 int main()
28 {
29     cin.sync_with_stdio(false);
30     int n , x , y , z , sum;
31     while( cin >> n )
32     {
33         sum = 0;
34         memset( in , 0 , sizeof(in) );
35         for( int i = 1 ; i<=n ; i++ )
36         {
37             cin >> val[i];
38             ve[i].clear();
39         }
40         while(1)
41         {
42             cin >> x >> y;
43             ve[y].push_back(x);
44             in[x] ++;
45             if( !x && !y )
46                 break;
47         }
48         for( int i =1 ; i<=n ; i++ )
49         {
50             if( !in[i] )
51             {
52                 z = i;
53                 break;
54             }
55         }    
56         dfs(z);
57         cout << max(dp[0],dp[1]) << endl;
58     }
59     return 0;
60 }

View Code

他还写了种多叉树转2叉树后的写法我感觉其实这个区别不算大吧..

但其实核心都是开头提到的状态转移方程

today:

　　听到一些事

　　明明和你不相关

　　但是能在心理拐几个弯的想到你

just follow your heart