首页 > 代码库 > hdu--1520--树形dp<写起来就是深搜啊>
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 }
today:
听到一些事
明明和你不相关
但是能在心理拐几个弯的想到你
hdu--1520--树形dp<写起来就是深搜啊>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。