标签 DP 下的文章

Archived | 307-15-背包的二进制优化

307-15-背包的二进制优化 P2851 [USACO06DEC]最少的硬币The Fewest Coins 题目描述 Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that t...

gyro永不抽风

2020 年 03 月 01 日

暂无评论

Archived | 307-13-子集枚举DP

307-13-14-子集枚举DP P3959 宝藏题目描述参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 $n$ 个深埋在地下的宝藏屋，也给出了这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度。小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。小明的决心感动了...

gyro永不抽风

2020 年 03 月 01 日

暂无评论

Archived | 307-08-背包应用

307-08-背包 P2160 [SHOI2007]书柜的尺寸题目描述 Tom不喜欢那种一字长龙式的大书架，他只想要一个小书柜来存放他的系列工具书。Tom打算把书柜放在桌子的后面，这样需要查书的时候就可以不用起身离开了。显然，这种书柜不能太大，Tom希望它的体积越小越好。另外，出于他的审美要求，他只想要一个三层的书柜。为了物尽其用，Tom规定每层必须至少放一本书。现在的问题是，Tom怎么...

gyro永不抽风

2020 年 03 月 01 日

暂无评论

307-07-逐行递推逐行递推： $d p$ 在某种情况下按照一行一行的顺序进行递推。 P2704 [NOI2001]炮兵阵地题目描述司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图...

gyro永不抽风

2020 年 03 月 01 日

暂无评论

Archived | 307-01-树形背包

307-01-树形背包 $O (n^{2})$ 算法 P2014选课题目描述在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的...