华师一附中OI组
标题:
DP大楼
[打印本页]
作者:
admin
时间:
2018-5-11 17:15
标题:
DP大楼
最简单的是递推，后面的由前面的几个计算得到，比如：等差等比数列，二阶等差，斐波那契，杨辉三角，卡特兰数，斯特林数等，不涉及比较，直接硬推。
注意这个推的过程，有的是一次就可以搞定，有的需要几轮。
P1077 摆花
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36070
P1057 传球游戏
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36069
连环炸弹
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36049
比这难一点的是每次决策过程中不是简单的累加而是有比较，比如
筷子
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36143
最长不下降序列LICS 导弹飞机
http://www.hsyit.cn/forum.php?mod=viewthread&tid=3659
P1233 木棍加工 LICS改进
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36205
P1650 田忌赛马
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36144
P2725 邮票 Stamps
http://hsyit.cn/forum.php?mod=viewthread&tid=36027
再复杂一点的就是二维表DP 要多次扫描，一轮轮的，简单的就是填一个表的过程，注意细节。当然有的可以迭代或者使用滚动数组变成一维数组但是本质还是多轮推。
杨辉三角 （滚动DP） 这里要认真体会二维数组做法，滚动数组，和反向数组递推的做法
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36058
数字三角形
http://hsyit.cn/forum.php?mod=viewthread&tid=36405
乘积最大
http://www.hsyit.cn/forum.php?mod=viewthread&tid=35999
最大的算式
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36055
最长公子序列 回文串 最长公共子序列的变形使用
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36212
相似基因
经典背包问题 它也算二维表型DP，注意我的那个推导过程， 特别是如何用一维数组的。
基础背包采药
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36061
疯狂的采药
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36000
开心的金明
http://www.hsyit.cn/forum.php?mod=viewthread&tid=35890
金明的预算
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36060
背包加强版
P1794 装备运输
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36146
P1509 找啊找啊找GF
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36134
氧气瓶氮气瓶
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36015
P2736 “破锣摇滚”乐队
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36147
P1095 守望者的逃离
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36003
P2725 邮票 Stamps
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36027
P1782 旅行商的背包
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36002
很难的背包
P1757 通天之分组背包
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36148
区间DP
P1063 能量项链
http://www.hsyit.cn/forum.php?mod=viewthread&tid=3669
P1880 [NOI1995]石子合并
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36126
树上DP
P1040 加分二叉树
http://www.hsyit.cn/forum.php?mod=viewthread&tid=36150
状压DP
http://hsyit.cn/forum.php?mod=viewthread&tid=36305
作者:
admin
时间:
2018-6-29 18:08
数字图形及其变形类
1、杨辉三角
2、数字三角形 P1216 [USACO1.5]数字三角形 Number Triangles
3、方格取数 P1004 方格取数
4、
作者:
admin
时间:
2018-6-29 18:08
简单背包类DP
采药装箱
开心的金明
砝码问题
欢迎光临 华师一附中OI组 (http://hsyit.cn/)
Powered by Discuz! X3.2