子串和子序列

子序列：子序列是在原来序列中找出一部分组成的序列。子序列不一定连续。
子串：字符串中任意个连续的字符组成的子序列称为该串的子串。子串一定连续。

1 小水獭和最大值1

题目

• 给定整数序列
• 求非空不相邻子序列元素和的最大值

解

状态转移方程：
表示计算到 时当前的求非空不相邻子序列元素和的最大值

2 小水獭和最大值2

题目

• 给定一个 的矩阵
• 初始时位于 ，目标位置为
• 每次可以向下移动或向右移动，即从 或
• 求经过位置元素之和的最大值

解

状态转移方程：

表示计算到 时当前的经过位置元素之和的最大值

3 7sozx特有的字符串

题目

• 设字符串
• 设 表示字符串 与 相同的位置数量，例如
• 给定字符串 ，求 的一个划分 ，满足 ，且 最大

解

• 设 表示字符串 的前 个字符所能得到的最大值
• 容易发现划分的每段长度都不超过
  状态转移方程：
  表示 的长度

4 杀戮尖塔

题目

• n层游戏，每层有编号为 的 个关卡。
• 玩家通过一关后可以进入下一层 个关卡中任意一个， 通过 层后结束。
• 要求相邻两层不能挑战相同编号的关卡。
• 给定 ，要求这些层不可进入第 关。 求通过 层的不同路线条数对998244353取模的结果。
• ，，

解

• 设 表示通过前 层，且在第 层是否选择第 关的路线数， 表示不选择第 关， 表示选择
  状态转移方程：
  第层不可进入第关第层可以进入第关

5 回文串串文回

题

• 给定长度为 的仅包含小写英文字母的字符串 。
• 每次操作可以向 中任意位置插入任意一个字符。
• 问最少需要多少次操作，能使操作后的字符串是回文串。
• 回文串指从左往右读和从右往左读相同的字符串。

解

设 表示 的第 个字符到第 个字符构成的子串变成回文串的最少操作次数。
状态转移方程：

6 任务达人莫卡2

题

• 有 个城市，初始时位于城市 。
• 第 天在城市 有任务，若接受任务，当前位于城市 可获得 收益，位于其他城市则前往城市 并获得 收益。
• 放弃任务不会获得收益，并停留在原所在城市。
• 求出 天后可获得的最大收益。
• ，

解

• 设 表示第 天结束后位于城市 时的最大收益
• 若第 天完成任务：
• 若第 天不完成任务，则有
• 从第 天转移到第 天仅需考虑 的变化
• 维护全局最大值和次大值，从而快速求出

7 Malicious Mischance

题

• 无限长的一维数轴上会出现 枚金币。
• 第 枚金币仅在时刻 出现在整点 ，仅当时刻 位于 时才能获得金币。
• 初始时时刻 ，位置为 。每个时刻可以选择不移动，或是向正方向移动一单位距离。也即，时刻 位于 ，则时刻 需要位于 之一。
• 求最多能拿到的金币枚数。
• ，。
  \

解

• 考虑拿到金币 之后还能拿到金币 需要满足的条件： 且
• 第二个不等式移项可得
• 将金币权值定义为
• 金币按 排序后，题目即是求 最长上升子序列的长度
• 注意要删除 的金币