CQU&SCU Union Training II - Dynamic Programming

前言

DP专题。斜率优化,单调队列,还有各种迷之姿势,反正这个专题我是废了Orz。


A. 雷神之路

题意

询问从0到n一共有多少种走法,每次可以走1、2、3步,有些点不能走。($1 \leq n \leq 10^18$)

分析

  1. 很容易想到dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3],然后地雷点dp[i] = 0。
  2. 华丽丽的由于矩阵乘法矩阵位置不对debug了好久。另外一直不知道怎么处理地雷,其实地雷就是原先的矩阵得出的下一个的值为0,那么根据这点构造地雷矩阵即可。

思考

  1. 坑点: 无。
  2. 技巧: 使用矩阵快速幂。分A类矩阵、B类矩阵计算。

C. TaoSama与煎饼

题意

煎饼工作台有($1 \leq n \leq 350$)的格子,煎饼通过每个格子会提升口感ai,初始时煎饼在位置1,所以初始口感度为a1。然而煎饼不能自己移动,必须使用Taosama的($1 \leq m \leq 120$)个小道具才能移动,每个小道具只能使用一次,每次移动距离bi($1 \leq bi \leq 4$),保证同样距离的小道具总数不超过40。

分析

  1. 格子,移动,第一个想法是背包,开搞,答案怎么不对= =额,使用顺序会影响结果啊!ZZ。
  2. 怎么存这顺序呢= =,重新看题目,移动距离1到4,不超过40,关键字啊,新状态dp[i][j][k][l]移动到i使用了第一个、第二个、第三个道具的数量,嗯,第四个相减就能出来嘛~不过这种状态爆内存啊!GG。
  3. 问fly我爆内存了咋办,他说开三维就够了。于是豁然开朗,第一维位置没用啊!然后搞,诶,怎么样例二答案不对= =。左思右想,不对啊,得四维,第四个道具不能由前三个计算出来,算了下不会爆内存,搞!然后AC了~

思考

  1. 坑点: 没有吧
  2. 技巧: 正如PPT所说,不管别的,状态开出来再说,优化等开出来后再考虑。

E. Goozy的积木

题意

用($1 \leq n \leq 50$)个积木,最高能搭建多高的两个塔?

分析

  1. 这不正是ppt上说的那道题吗?dp[i][j]代表到第i个积木,两塔高度差为j时,最大的共同高度,那么答案就是dp[n][0]了。初始化dp[0][0]为0,其它为负无穷(都是不合法状态)
  2. 转移写了半天,最后自己都搞混了。自己定义的状态没有记清楚,搞得debug了半天。

思考

  1. 坑点: 没有。
  2. 技巧: 一定要记得自己状态代表的含义啊!!!$\times 3$

H. 又见背包

题意

有($1 \leq n \leq 100$)种大小不同的数字a_i,每种($1 \leq m_i \leq 10^9$)个,判断是否可以从这些数字中选出若干使它们的和恰好为($1 \leq k \leq 10^5$)。

分析

  1. 诶!这不是男人八题?!多重背包 + 二进制优化 + bool型dp。
  2. 出题组说二进制优化会被卡!不管了,先写T了再说。结果AC,时间72ms。饿= =。

思考

  1. 坑点: 没有。
  2. 技巧: 使用bool型进行转移的话,比起平常调用max函数效率要快不少。另外,本题正解应该是多重背包的单调队列优化,复杂度O(V*N)。然而这种科技就留给fly和xf去吧,2333。

L. 来签个到吧

题意

初始有n个球,球上写着数字,第一阶段的任务是让任意两个球上数字之差都在这些球上出现(通过添加球办到),此阶段操作数固定,为放进球的个数;第二阶段需要任意从中抽出球,抽出后放回,直到所有数字都被拿出。问:两阶段的操作数期望值是多少?

分析

  1. 第一阶段的任务就是把原始的数列变成等差数列,求公共gcd即可。
  2. 第二阶段要算期望了,默默想到一个状态,dp[i]代表拿到i张卡片的期望操作数,发现无法转移,GG。于是就上网查资料,发现了这个有趣的链接:传送

思考

  1. 坑点: 数列中的值存在0,此时不能把0考虑进入gcd。
  2. 技巧: 说好的dp呢?转移呢?怎么就变成解数学期望题了!!!把取到第i个数的平均次数相加就是期望次数,果然高中到现在,还是觉得概率啊,期望啊这种东西太迷了。

具体代码点击下方传送门:)

传送门


广告时间

Java学习网站: how2j

VPS: VPS

梦想世界上每个人都能给我一元钱,2333