高度由习惯堆积

分类 算法:基础dp 下的文章

NOI2009 诗人小G

题目小G是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小G不允许把一个句子分在两行或...
February 16, 2019

Topcoder10073 SRM418 BarracksEasy

这题最困难的方面是战斗的策略。假设我们有$i$个士兵,兵营的血量为$z$,我们的对手有$j$个士兵,设$dp[i][j][k]$为我们赢得战斗的最小回合数(如果不可能,则为无穷)。计算时,按照题目的步骤一步步模拟递推就行了。但是如果只是这样的话,可能会出现环,或者无穷的状态(比如$j$不断往上增长),所以为了解决这一点,需要将$j>100$的情况全部舍弃。具体细节请看代码#includ...