Loading...
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...
307-13-14-子集枚举DP P3959 宝藏 题目描述 参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了$n$个深埋在地下的宝藏屋， 也给出了这$n$个宝藏屋之间可供开发的$m$条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。 小明的决心感动了...
307-08-背包 P2160 [SHOI2007]书柜的尺寸 题目描述 Tom不喜欢那种一字长龙式的大书架，他只想要一个小书柜来存放他的系列工具书。Tom打算把书柜放在桌子的后面，这样需要查书的时候就可以不用起身离开了。 显然，这种书柜不能太大，Tom希望它的体积越小越好。另外，出于他的审美要求，他只想要一个三层的书柜。为了物尽其用，Tom规定每层必须至少放一本书。现在的问题是，Tom怎么...
307-07-逐行递推 逐行递推：$dp$在某种情况下按照一行一行的顺序进行递推。 P2704 [NOI2001]炮兵阵地 题目描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图...
307-01-树形背包$O(n^2)$算法 P2014选课 题目描述 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的...