POJ 2486 Apple Tree ( 树型DP )

POJ 2486 Apple Tree ( 树型DP )

大家好,又见面了,我是全栈君。

#include <iostream>
#include <cstring>
#include <deque>
using namespace std;

#define SIZE 230
#define BACK 1
#define AWAY 0

int DP[SIZE][SIZE][2];
bool visits[SIZE];
int vals[SIZE];
deque< int > tree[SIZE];

int num, steps;


void dfs( int u ){

    visits[u] = true;
    const int len = tree[u].size();

    for( int i = 0; i <= steps; ++i )
        DP[u][i][BACK] = DP[u][i][AWAY] = vals[u];

    for( int i = 0; i < len; ++i ){

        int son = tree[u][i];

        if( visits[son] )
            continue;

        dfs( son );

        for( int s = steps; s >= 0; --s ){
            for( int ss = 0; ss <= s; ++ss ){
                /*
                    从 u 出发,回到 u。须要多走两步 u->son,son->u,
                    分配给 son 子树 ss 步,其它子树 s - ss 步。都返回.
                */
                DP[u][s + 2][BACK] = max( DP[u][s + 2][BACK],
                                          DP[u][s - ss][BACK] + DP[son][ss][BACK] );

                /*
                    不回 u (去 u 的其它子树)。在 son 返回.
                */
                DP[u][s + 2][AWAY] = max( DP[u][s + 2][AWAY],
                                          DP[u][s - ss][AWAY] + DP[son][ss][BACK] );

                /*
                    先遍历 u 的其它子树,回到 u 后,遍历 son 子树,
                    在当前子树 son 不返回,多走一步.
                */
                DP[u][s + 1][AWAY] = max( DP[u][s + 1][AWAY],
                                          DP[u][s - ss][BACK] + DP[son][ss][AWAY] );

            }
        }
    }
}


int main(){

    int u, v;

    while( cin >> num >> steps ){

        memset( DP,     0,     sizeof( DP ) );
        memset( visits, false, sizeof( visits ) );

        for( int i = 1; i <= num; ++i )
            tree[i].clear();

        for( int i = 1; i <= num; ++i )
            cin >> vals[i];

        for( int i = 1; i <= num - 1; ++i ){

            cin >> u >> v;

            tree[u].push_back( v );
            tree[v].push_back( u );

        }

        dfs( 1 );

        cout << max( DP[1][steps][BACK], DP[1][steps][AWAY] ) << endl;

    }

    return 0;

}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116052.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号