技能树上的dp问题

2024-06-04 22:32
文章标签 问题 dp 树上 技能

本文主要是介绍技能树上的dp问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

热爱电子娱乐的同学们对于技能树一定不陌生.就是说,要先学习低级的垃圾技能,特定
的几个垃圾技能学会了,才能学习更强的技能.比如说,要先学火球术和烈火墙,才能学习地狱
烈焰.科技树也是一样.要先研究出电力和内燃机,才能研究工业学.那么,现在我们把问题简化,
这是一个技能树(或者科技树).格子上的数,是威力值.要先学会第一排第二个和第三个,才能
学会第二排的第二个.每个技能学习的前提都是左上和右上的两个技能.假设现在有一个第一
层有N 个技能的技能树,而且技能点是有限的,只能学习M 个技能,我们想知道最大的威力值
之和是多少.
这里写图片描述
(ps:这个不是样例)

Input Format

第一行两个数N 和M,如题所述
之后N 行,第i 行,有n+1-i 个数.表示一个技能树.

Output Format

输出一个数,表示最大威力值之和

Sample Input

4 5
1 1 1 1
1 2 1
1 1
1

Sample Output

6

Data Limit

对于40%的数据,N<=10
对于100%的数据,N<=50,M<=500,所有数据都在int 之内.

技能树上的dp是一种不容易想到的dp问题,因为这种树状结构的dp大家都很熟悉,拿到这道题很容易就想成了树规或者从上向下,从下向上之类的dp问题,但是看到这道题的数据范围又是这么小,一看就有问题,然后就卡住了,最后只能写一个 O(2n) 的暴力。
那么现在我们仔细看看一下这道题,因为dp要无后效性(当前的状态只与前一个状态有关,而再前面的状态影响不了当前的状态,当前的状态也只能影响它后面的状态,不能影响再后面的状态),而如果我们从上向下dp的话,能不能去某一个数必须要看它上面的伞状结构的那一部分取没有,完全没法正常dp,方程一直列不出来。
我们就开始考虑,如何是我们的dp达到无后效性呢?
仔细观察我们可以发现无论我们怎么取,轮廓线都是一条锯齿状的折线。
这里写图片描述
我们发现每一列只有一个点在轮廓线上,而这些点,就是我们可以用来dp的点。
我们考虑从左向右dp,每一个在轮廓线上面的点只能有它前一列的上面或者下面得来,符合dp的无后效性
如上图,我们设“14”在第一行第一列,“33”在第二行第二列密码“15”在第一行第三列
而如果取一个点,也就说明要取它上面的所有点,我们可以先预处理将每个点上面点的数量存在num数组,价值和存在sum数组,f[k][i][j]表示[i][j]轮廓线取到这个坐标,一共取了k个数的最大值,然后开始状态转移!

这篇关于技能树上的dp问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1031301

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

uva 10154 DP 叠乌龟

题意: 给你几只乌龟,每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析: 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠,状态转移方程: dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]

uva 10118 dP

题意: 给4列篮子,每次从某一列开始无放回拿蜡烛放入篮子里,并且篮子最多只能放5支蜡烛,数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时,猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs