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)


相关推荐

  • Excel 日期和时间函数[通俗易懂]

    Excel 日期和时间函数[通俗易懂]1、TODAY和NOW函数today和now函数日期可以进行加减运算2、提取日期和时间的函数双击右下自动填充完!!!3、WEEKDAY函数weekday函数4、DATEDIF函数

  • laravel框架手机发送验证码

    laravel框架手机发送验证码

    2021年10月25日
  • 箭头函数与普通函数的区别详解[通俗易懂]

    箭头函数与普通函数的区别详解[通俗易懂]箭头函数和普通函数的区别一.外形不同:箭头函数使用箭头定义,普通函数中没有代码实例如下://普通函数functionfunc(){//code}//箭头函数letfunc=()=>{//code}二.箭头函数都是匿名函数普通函数可以有匿名函数,也可以有具体名函数,但是箭头函数都是匿名函数。代码实例如下://具名函数functionfunc(){//code}//匿名函数letfunc=function(){//cod

  • C#时间控件[通俗易懂]

    C#时间控件[通俗易懂]1、添加DateTimerPicker控件2、代码:dateTimePicker1.Format=DateTimePickerFormat.Custom;//设置Format属性为Custom,使用户自定义的时间格式生效dateTimePicker1.CustomFormat=”MMMMdd,yyyy-dddd”

  • TCP报文格式详解

    TCP报文是TCP层传输的数据单元,也叫报文段。端口号:用来标识同一台计算机的不同的应用进程。源端口:源端口和IP地址的作用是标识报文的返回地址。目的端口:端口指明接收方计算机上的应用程序接口。TCP报头中的源端口号和目的端口号同IP数据报中的源IP与目的IP唯一确定一条TCP连接。序号和确认号:是TCP可靠传输的关键部分。序号是本报文段发送的数据组的第一个字节的序号。

  • system在c语言中_c语言system返回值

    system在c语言中_c语言system返回值需包含头文件:C标准库-<stdlib.h>文章目录描述声明参数返回值实例1实例2:列出windows机上当前目录下所有的文件和目录描述C库函数intsystem(constchar*command)把command指定的命令名称或程序名称传给要被命令处理器执行的主机环境,并在命令完成后返回。声明下面是system()函数的声明。intsystem(constchar*command)参数command–包含被请求变量名称的C字符串。

发表回复

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

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