[树形dp] POJ2486

题意

一颗树，n个点（1-n），n-1条边，每个点上有一个权值，求从1出发，走V步，最多能遍历到的权值

思路

0代表s出发回到s, 1代表s出发不回来
初始化每个rt的每个步长都是当前节点的权值
dp[root][j][0] = MAX (dp[root][j][0] , dp[root][j-k][0] + dp[son][k-2][0]);//从s出发，要回到s，需要多走两步s-t,t-s,分配给t子树k步，其他子树j-k步，都返回
dp[root][j]][1] = MAX( dp[root][j][1] , dp[root][j-k][0] + dp[son][k-1][1]) ;//先遍历s的其他子树，回到s，遍历t子树，在当前子树t不返回，多走一步
dp[root][j][1] = MAX (dp[root][j][1] , dp[root][j-k][1] + dp[son][k-2][0]);//不回到s（去s的其他子树），在t子树返回，同样有多出两步

之所以1需要有两个式子
因为第一种不返回的是之前找到的孩子
第二种是当前孩子

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int INF = 0x7f7f7f7f;
const int maxn = 100 + 10;
int n, k;
int val[ maxn ];
int dp[ maxn ][ 2 * maxn ][ 2 ];
bool vis[ maxn ];
struct EDGE {
int to, nex, id;
} edg[ 2 * maxn ];
int cnt;
int head[ maxn ];
void INit () {
cnt = 0;
memset ( dp, 0, sizeof ( dp ) );
memset ( head, -1, sizeof ( head ) );
memset ( edg, 0, sizeof ( edg ) );
memset ( vis, false, sizeof ( vis ) );
}
void AddEdge ( int u, int v ) {
edg[ cnt ].to = v;
edg[ cnt ].nex = head[ u ];
head[ u ] = cnt++;
}
void tree_dp ( int rt ) {
vis[ rt ] = true;
for ( int i = 0; i <= k; ++i )
dp[ rt ][ i ][ 0 ] = dp[ rt ][ i ][ 1 ] = val[ rt ];
for ( int i = head[ rt ]; i != -1; i = edg[ i ].nex ) {
int son = edg[ i ].to;
if ( !vis[ son ] ) {
tree_dp ( son );
for ( int j = k; j >= 1; --j )
for ( int l = 1; l <= j; ++l ) {
if ( l >= 2 )
//从s出发,经过之前的孩子,回到s,经过当前扫描的孩子,再回到s
dp[ rt ][ j ][ 0 ] = max (
dp[ rt ][ j ][ 0 ], dp[ rt ][ j - l ][ 0 ] + dp[ son ][ l - 2 ][ 0 ] );
if ( l >= 1 )
//从s出发,经过之前的孩子,回到s,经过当前扫描的孩子
dp[ rt ][ j ][ 1 ] = max (
dp[ rt ][ j ][ 1 ], dp[ rt ][ j - l ][ 0 ] + dp[ son ][ l - 1 ][ 1 ] );
if ( l >= 2 )
//从s出发,经过当前扫描的孩子,回到s,经过之前的孩子
dp[ rt ][ j ][ 1 ] = max (
dp[ rt ][ j ][ 1 ], dp[ rt ][ j - l ][ 1 ] + dp[ son ][ l - 2 ][ 0 ] );
}
}
}
}
int main () {
#ifdef LOCAL
freopen ( "in", "r", stdin );
// freopen("out","w",stdout);
#endif
while ( ~scanf ( "%d%d", &n, &k ) ) {
INit ();
for ( int i = 1; i <= n; ++i )
scanf ( "%d", &val[ i ] );
for ( int i = 0, u, v; i < n - 1; ++i ) {
scanf ( "%d%d", &u, &v );
AddEdge ( u, v );
AddEdge ( v, u );
}
tree_dp ( 1 );
printf ( "%dn", dp[ 1 ][ k ][ 1 ] );
}
return 0;
}

最后

以上就是内向天空为你收集整理的[树形dp] POJ2486的全部内容，希望文章能够帮你解决[树形dp] POJ2486所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。