poj2486 Apple Tree （树形dp）

题意：有一颗苹果树，树上的u节点上有num[u]个苹果，树根为1号节点，囧king从根开始走，没走到一个节点就把接点上的苹果吃光，问囧king在不超过k步的情况下最多吃多少个苹果。

解题思路：处理出两个dp数组，f1[u][i]表示在不超过i步的情况下，从u节点开始，往下吃，吃完后回到u节点，最多能吃多少苹果。f2[u][i]表示在不超过i步的情况下，从u节点开始往下吃，最多能吃多少苹果。

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std ;

const int maxn = 111111 ;

int max ( int a , int b ) { return a > b ? a : b ; }

int min ( int a , int b ) { return a < b ? a : b ; }

struct Edge

{

	int to , next ;

} edge[maxn<<1];

int head[maxn] , tot , n , m ;

int f1[111][2222]  , f2[111][222] , num[maxn] , ans , dis[1111] ;

void new_edge ( int a , int b )

{

	edge[tot].to = b ;

	edge[tot].next = head[a] ;

	head[a] = tot ++ ;

	edge[tot].to = a ;

	edge[tot].next = head[b] ;

	head[b] = tot ++ ;

}

int c[111][222] , d[maxn] , l ;

void dfs ( int u , int fa , int *f )

{

	int i , j , k ;

	if ( u != 1 )

	{

		for ( i = dis[u] ; i <= m ; i ++ )

			ans = max ( ans , f2[u][m-i] + f[i] ) ;

	}

	int fuck[222] ;

	for ( i = head[u] ; i != -1 ; i = edge[i].next )

	{

		int v = edge[i].to ;

		if ( v == fa ) continue ;

		for ( j = 0 ; j <= m ; j ++ ) d[j] = 0 ;

		int t = 0 ;

		for ( j = head[u] ; j != -1 ; j = edge[j].next )

		{

			if ( edge[j].to == v || edge[j].to == fa ) continue;

			t ++ ;

			for ( k = 0 ; k <= m ; k ++ )

				c[t][k] = f1[edge[j].to][k] ;

		}

		for ( j = 1 ; j <= t ; j ++ )

			for ( k = m ; k >= 0 ; k -- )

				for ( l = 0 ; l + 2 <= k ; l ++ )

					d[k] = max ( d[k] , d[k-l-2] + c[j][l]  ) ;

		for ( j = 0 ; j <= m ; j ++ ) fuck[j] = 0 ;

		for ( j = dis[u] ; j < m ; j ++ ) fuck[j+1] = f[j] ;

		for ( j = dis[u] ; j <= m ; j ++ )

			for ( k = 0 ; k <= m ; k ++ )

				if ( j + k + 1 <= m )

					fuck[j+k+1] = max ( fuck[j+k+1] , f[j] + d[k] + num[u] ) ;

		dfs ( v , u , fuck ) ;

	}

}

void cal ( int u , int fa )

{

	int i , j , k ;

	for ( i = head[u] ; i != -1 ; i = edge[i].next )

	{

		int v = edge[i].to ;

		if ( v == fa ) continue ;

		dis[v] = dis[u] + 1 ;

		cal ( v , u ) ;

		for ( k = m ; k >= 0 ; k -- )

			for ( j = 0 ; j + 2 <= k ; j ++ )

				f1[u][k] = max ( f1[u][k] , f1[u][k-j-2] + f1[v][j] ) ;

		for ( k = 1 ; k <= m ; k ++ ) f2[u][k] = max ( f2[u][k] , f2[v][k-1] ) ;

		for ( j = 0 ; j <= m ; j ++ ) d[j] = 0 ;

		int t = 0 ;

		for ( j = head[u] ; j != -1 ; j = edge[j].next )

		{

			if ( edge[j].to == v || edge[j].to == fa ) continue ;

			t ++ ;

			for ( k = 0 ; k <= m ; k ++ )

				c[t][k] = f1[edge[j].to][k] ;

		}

		for ( j = 1 ; j <= t ; j ++ )

			for ( k = m ; k >= 0 ; k -- )

				for ( l = 0 ; l + 2 <= k ; l ++ )

					d[k] = max ( d[k] , d[k-l-2] + c[j][l]  ) ;

		for ( j = 0 ; j <= m ; j ++ )

			for ( k = 0 ; k + 1 <= j ; k ++ )

				f2[u][j] = max ( f2[u][j] , f2[v][k] + d[j-k-1] ) ;

	}

	for ( i = 0 ; i <= m ; i ++ ) f1[u][i] += num[u] , f2[u][i] += num[u] ;

	for ( i = 1 ; i <= m ; i ++ ) f1[u][i] = max ( f1[u][i] , f1[u][i-1] ) , f2[u][i] = max ( f2[u][i] , f2[u][i-1] ) ;

}

void init ()

{

	int i ;

	memset ( head , -1 , sizeof ( head ) ) ;

	memset ( f1 , 0 , sizeof ( f1 ) ) ;

	memset ( f2 , 0 , sizeof ( f2 ) ) ;

	memset ( dis , 0 , sizeof ( dis ) ) ;

	tot = ans = 0 ;

}

int f[222] ;

int main ()

{

	int i , j , k , a , b ;

	while ( scanf ( "%d%d" , &n , &m ) != EOF )

	{

		init () ;

		for ( i = 1 ; i <= n ; i ++ ) scanf ( "%d" , &num[i] ) ;

		for ( i = 1 ; i < n ; i ++ )

		{

			scanf ( "%d%d" , &a , &b ) ;

			new_edge ( a , b ) ;

		}

		cal ( 1 , 0 ) ;

		ans = f2[1][m] ;

		for ( i = 0 ; i <= m ; i ++ ) f[i] = 0 ;

		dfs ( 1 , 0 , f ) ;

		printf ( "%d\n" , ans ) ;

	}

}

巴特西

poj2486 Apple Tree （树形dp）

最新文章

热门文章