动态规划-java语言练习一:暴力DP
重新进行算法的一个卷,主要复习高二学的动态规划知识(
练习题目参考洛谷提单:【动态规划】普及~省选的DP题 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
练习暴力DP主要是先找回DP的感觉,练习推转移方程。
T1. 乌龟棋 线性DP
[P1541 NOIP2010 提高组] 乌龟棋 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目讲从起点到终点,每个点有不同的分数,有指定数量的1,2,3,4号牌,每张最多用一次,用几号牌乌龟就走几格。求能获得的最高分数。
设num[i]
为i处的分数,count[i]
为某号牌的张数。
分状态
可以看出状态可以由使用不同种牌的次数来划分,因此设s[a][b][c][d]
为使用了a张1号,b张2号...牌能取得的最高分数。
显然,s[0][0][0][0]
=num[1]
,我们要求的就是s[num_a][num_b]...
的值。
转移方程
对于某种牌,只有使用和不使用两种选择。因此,对于1号牌:
其中,。(注意起点编号是1,所以r要先+1)
同理,可推得总的状态转移方程:
即某状态可以由少使用一张某种牌+这个状态对应的地图上的点的分数来得到。
当然,由于输入说可能没有某种牌(a=0,b=0,...),代码实现的时候我们只能把这四种牌的转移方程拆开写。
代码
T2. 樱花 多重背包
最后更新于