前言

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

A. 雷神之路

题意

询问从0到n一共有多少种走法，每次可以走1、2、3步，有些点不能走。(1≤n≤10181 \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≤n≤3501 \leq n \leq 350)的格子，煎饼通过每个格子会提升口感ai，初始时煎饼在位置1，所以初始口感度为a1。然而煎饼不能自己移动，必须使用Taosama的(1≤m≤1201 \leq m \leq 120)个小道具才能移动，每个小道具只能使用一次，每次移动距离bi(1≤bi≤41 \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≤n≤501 \leq n \leq 50)个积木，最高能搭建多高的两个塔？

分析

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

思考

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

H. 又见背包

题意

有(1≤n≤1001 \leq n \leq 100)种大小不同的数字a_i,每种(1≤mi≤1091 \leq m_i \leq 10^9)个，判断是否可以从这些数字中选出若干使它们的和恰好为(1≤k≤1051 \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