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)


相关推荐

  • 多多客发布 3.0.0-alpha.3开源版,支持微信、百度、支付宝小程序

    多多客发布 3.0.0-alpha.3开源版,支持微信、百度、支付宝小程序

  • 单射(或称单变换)、双射与满射

    单射(或称单变换)、双射与满射单射(或称单变换)、双射与满射原文链接:http://www.cnblogs.com/wanghetao/archive/2012/03/16/2400619.html数学上,单射、满射和双射指根据其定义域和陪域的关联方式所区分的三类函数。单射:指将不同的变量映射到不同的值的函数。满射:指陪域等于值域的函数。即:对陪域中任意元素,都存在至少一个定义域中的元素与之对应。双射(

  • MIPI协议知识

    MIPI协议知识转发路径:https://blog.csdn.net/weixin_41842559/article/details/109828013?spm=1001.2101.3001.6650.14&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-14.pc_relevant_paycolumn_v3&depth_1-utm_source=distribute.pc_

  • 我的书单

    整理了一下自己购物车里的书单,推荐一下。

  • 【懒人必备】智能窗帘机器人,告别手动拉窗帘——硬件设计篇

    【懒人必备】智能窗帘机器人,告别手动拉窗帘——硬件设计篇简介:智能窗帘机器人方案,无需专业人员上门安装,使普通窗帘秒变智能窗帘。概述随着智能家居的深入拓展,智能窗帘凭借成熟的技术和产品,逐步成为了智能家居家庭中的标配,在家装智能化市场有很高的应用价值。目前智能窗帘的产品主要以电动窗帘产品为主,该产品主要通过电机驱动实现对窗帘的操控,从安装上讲,该产品更适合前装市场,因为需要结合用户户型、门窗大小预留安装空间和电源接口。对于后装市场,往往需要专业人员上门丈量确认是否符合改装要求,大大增加了安装成本,因此目前市场上,出现的小型的窗帘机器人,完美解决的后装市场的

  • 软件详细设计说明书 模板「建议收藏」

                                             软件详细设计说明书1引言1.1编写目的:阐明编写详细设计说明书的目的,指明读者对象。1.2项目背景:应包括项目的来源和主管部门等。1.3定义:列出本文档中所用到的专门术语的定义和缩写词的愿意。1.4参考资料:  ●列出有关资料的作者、标题、编号、发表日期、出版单位或资料来源  ●项

发表回复

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

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