DP:树DP

DP:树DP

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

The more, The Better

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5414    Accepted Submission(s): 3217




Problem Description
ACboy非常喜欢玩一种战略游戏,在一个地图上,有N座城堡。每座城堡都有一定的宝物,在每次游戏中ACboy同意攻克M个城堡并获得里面的宝物。但因为地理位置原因。有些城堡不能直接攻克,要攻克这些城堡必须先攻克其它某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗?

 


Input
每一个測试实例首先包含2个整数,N,M.(1 <= M <= N <= 200);在接下来的N行里。每行包含2个整数。a,b. 在第 i 行,a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡,假设 a = 0 则代表能够直接攻克第 i 个城堡。

b 代表第 i 个城堡的宝物数量, b >= 0。当N = 0, M = 0输入结束。

 


Output
对于每一个測试实例。输出一个整数。代表ACboy攻克M个城堡所获得的最多宝物的数量。
 


Sample Input
   
   
3 2 0 1 0 2 0 3 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 0 0

 


Sample Output
   
   
5 13

dp[i][j]表示以i为根节点j个子节点的最大值。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<vector>
typedef long long LL;
using namespace std;
const int maxn=220;
int v[maxn];
int n,m;
int dp[maxn][maxn];
vector<int>s[maxn];
void tree_dp(int n,int f)
{
    int len=s[n].size();
    dp[n][1]=v[n];
    for(int i=0;i<len;i++)
    {
        if(f>1)  tree_dp(s[n][i],f-1);
        for(int j=f;j>=1;j--)
        {
            for(int k=1;k<=j;k++)
                dp[n][j+1]=max(dp[n][j+1],dp[n][j+1-k]+dp[s[n][i]][k]);
        }
    }
}
int main()
{
    int f;
    while(~scanf("%d%d",&n,&m)&&(n+m))
    {
        v[0]=0;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=n;i++)
            s[i].clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&f,&v[i]);
            s[f].push_back(i);
        }
        tree_dp(0,m+1);
        printf("%d\n",dp[0][m+1]);
    }
    return 0;
}

Anniversary party

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 4329   Accepted: 2463

Description

There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests' conviviality ratings.

Input

Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go N – 1 lines that describe a supervisor relation tree. Each line of the tree specification has the form: 

L K 

It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line 

0 0 

Output

Output should contain the maximal sum of guests' ratings.

Sample Input

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

Sample Output

5

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
typedef long long LL;
using namespace std;
const int maxn=6005;
int dp[maxn][2],pre[maxn];
int visit[maxn],n;
void tree_dp(int x)
{
    visit[x]=1;
    for(int i=1;i<=n;i++)
    {
//        cout<<"111  "<<i<<endl;
        if(!visit[i]&&pre[i]==x)
        {
            tree_dp(i);
            dp[x][1]+=dp[i][0];
            dp[x][0]+=max(dp[i][1],dp[i][0]);
        }
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        memset(dp,0,sizeof(dp));
        memset(visit,0,sizeof(visit));
        memset(pre,0,sizeof(pre));
        for(int i=1;i<=n;i++)
           scanf("%d",&dp[i][1]);
        int x,y,root;
        while(~scanf("%d%d",&x,&y)&&(x+y))
        {
            pre[x]=y;
            root=y;
        }
        while(pre[root])
            root=pre[root];
 //       cout<<"fuck   "<<root<<endl;
        tree_dp(root);
        printf("%d\n",max(dp[root][0],dp[root][1]));
    }
    return 0;
}

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

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

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

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

(0)


相关推荐

  • Access 通用数据访问类(asp.net 2.0 c#)

    Access 通用数据访问类(asp.net 2.0 c#)

  • 视频识别分类算法–MASK-RCNN框架[通俗易懂]

    视频识别分类算法–MASK-RCNN框架[通俗易懂]基础内容

  • Linux lamp_lamp搭建和配置

    Linux lamp_lamp搭建和配置LAMP架构LAMP架构是目前成熟的企业网站应用模式之一,指的是协同工作的一整套系统和相关软件,能够提供动态Web站点服务及其应用开发环境。LAMP是一个缩写词,具体包括Linux操作系统、Apache网站服务器、MySQL数据库服务器、PHP(或Perl、Python)网页编码。在构建LAMP平台时,各组件的安装顺序依次为Linux、Apache、MySQL、PHP。其中…

    2022年10月17日
  • Struts2拦截器详解

    Struts2拦截器详解成功的花儿,其间浸透了奋斗的泪水和汗水;然而,用泪水和汗水就可以实现一切的美好。Struts2拦截器概述拦截器的概念是在Struts2里面有的。在其它地方没有。Struts2是框架,封装了很多的功能,struts2里面封装的功能都是在拦截器里面。Struts2里面封装了很多的功能,有很多拦截器,不是每次这些拦截器都执行,每次执行默认的拦截器。Struts2里面默认的拦截器位置:struts

  • java二维数组坐标_Java 二维数组

    java二维数组坐标_Java 二维数组二维数组的定义二维数组本质上是以数组作为数组元素的数组,即“数组的数组”。因为数组只能保存一行数据。在生活中,比如坐标等等,我们需要用二维数组来表示。通过行号和列好来定位数据。定义:类型数组[][]  类型[][]数组名例如:floata[3][4];  //定义a为3行4列的数组二维数组的声明和初始化二维数组的声明、初始化和引用与一维数组相似。当使用new来创建二维数组时,不必指定每一维的…

  • 10秒钟脱口而出十位数相同两位数的乘法

    10秒钟脱口而出十位数相同两位数的乘法10秒钟脱口而出十位数相同两位数的乘法一、范围十位数相同的两位数。二、目标计算两位数的相乘。10秒钟脱口而出。三、基本公式以尾数之和展开讨论:假设两个数分别是10a+b以及10a+c,那么尾数之和就是b+c。序号分类公式举例1尾数之和小于10即b+c(10a+b)(10a+c)=100a²+10a(b+c)+bc=10a((10a+b)+c)+bc  21X23=(20+1)(20+

发表回复

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

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