连续段 DP：为什么要以当前位置结尾

1 扫描到一个新元素时，需要知道什么？

给定一个数组，求最长的连续正数段。例如：

1
2

下标 i：  0   1   2   3   4   5   6
元素 a：  2   5  -1   3   4   6   0

答案是 3，对应连续的三个正数 [3, 4, 6]。

注意这里要求的是连续段：选中的元素在原数组中必须相邻，不能跳过中间的元素。全文下标都从 0 开始；没有符合条件的非空连续段时，答案记为 0。

最直接的做法是枚举起点，从每个起点向右扩展，遇到非正数就停止。如果所有元素都是正数，同一个位置会被不同起点反复扫描，总时间为 $O(n^2)$。

这些重复检查能否共用？

看从 3 开始的这一段：扫描到 4 时，已经知道它前面紧挨着一个正数；扫描到 6 时，只要知道前面紧挨着两个正数，就能得到新的长度。我们不必重新检查 3 和 4。

因此，扫描到位置 $i$ 时，真正需要的信息是：

紧挨着当前位置左边，已经有多少个连续正数？

这就把“寻找整个区间”的问题，变成了“能否用新元素延长上一段”的问题。

2 为什么定义“以 i 结尾”？

2.1 先把子问题说准确

定义：

如果 $a[i]\le 0$，就不存在以它结尾的非空连续正数段，令 $dp[i]=0$。

这里的“必须以 $i$ 结尾”很重要。它保证 $dp[i-1]$ 代表的连续段恰好紧挨着 $a[i]$，因此我们能够判断能不能把 $a[i]$ 接在它后面。

例如，扫描到前面数组的最后一个正数 6 时，我们关心的是紧邻它的 [3, 4]，而不是更早出现过的 [2, 5]。

2.2 再判断新元素能否接上

只有两种情况：

• $a[i]>0$：可以接在前一个连续正数段之后，长度加 1；如果前一段为空，就从当前位置开始一段。
• $a[i]\le 0$：任何包含当前位置的区间都不可能全是正数，当前连续段结束，长度归零。

于是得到：

为了统一公式，约定 $dp[-1]=0$。这是数学上的边界约定，代码里不能访问数组的 dp[-1]。

为什么正数时的答案恰好是 $dp[i-1]+1$？一方面，前一段接上当前正数，确实构成这么长的合法段；另一方面，任何以 $i$ 结尾的连续正数段，去掉最后一个元素，剩下的都是以 $i-1$ 结尾的连续正数段，不可能比 $dp[i-1]$ 更长。

这两方面一起说明，转移既不会漏掉更长的段，也不会算出不存在的段。

2.3 手算一遍状态

这里有两个不同的量：当前段有多长，以及到目前为止，最长的一段有多长。当前位置不合法时，第一个量变为 0，第二个量可以保持不变。

下面只给核心代码，假设已有长度为 n 的数组 a，并为 dp 分配了至少 n 个位置：

1
2
3
4
5
6
7
8
9
10
11
12

int ans = 0;
for (int i = 0; i < n; i++) {
    if (a[i] > 0) {
        dp[i] = 1;
        if (i > 0) {
            dp[i] += dp[i - 1];
        }
    } else {
        dp[i] = 0;
    }
    ans = max(ans, dp[i]);
}

一次扫描就算出了全部状态，时间复杂度为 $O(n)$，保存整个 dp 数组的额外空间为 $O(n)$。

3 为什么只记录“前面的最大值”不够？

另一种看起来很自然的定义是：

这里“前 $i$ 个位置”指下标 $0$ 到 $i-1$，因此 $f[0]=0$。

这个定义可以记录答案，却没有记录最长段在哪里结束。

把正数记为 1、非正数记为 0，比较两个前缀：

1
2

前缀 A：1 1 0
前缀 B：0 1 1

两者都有 $f[3]=2$。现在都在末尾接上一个 1：

1
2

A：1 1 0 1    最长连续 1 的长度仍然是 2
B：0 1 1 1    最长连续 1 的长度变成了 3

前缀最优值相同，新加入的元素也相同，但结果不同。这说明：只知道 $f[3]$ 和新元素，信息还不够，无法确定下一步的答案。

缺少的正是末尾连续段的长度：A 的末尾连续 1 长度为 0，B 为 2。

因此，我们先用 $dp[i]$ 记录能直接参与延续的状态，再用它更新前缀最优值：

定义状态时，不仅要考虑“它能不能表示最终答案”，还要考虑“它保留的信息，够不够推导下一个状态”。

4 换一种合法条件，还能这样设计吗？

4.1 最长连续相同字符段

例如字符串 aabbbaa，最长连续相同字符段是 bbb，长度为 3。

定义 $dp[i]$ 为以 $i$ 结尾的最长连续相同字符段长度。判断能否延续时，只需比较当前字符和前一个字符：

这里断开后为什么是 1？因为即使当前字符与前一个不同，单个字符本身仍然是合法的一段。

核心转移为：

1
2
3
4
5
6

for (int i = 0; i < n; i++) {
    dp[i] = 1;
    if (i > 0 && s[i] == s[i - 1]) {
        dp[i] = dp[i - 1] + 1;
    }
}

4.2 最长严格递增连续段

例如数组 [2, 4, 3, 5, 7, 1]，最长严格递增连续段是 [3, 5, 7]，长度为 3。

定义 $dp[i]$ 为以 $i$ 结尾的最长严格递增连续段长度。当 $a[i]>a[i-1]$ 时，当前元素可以接上前一段：

核心转移为：

1
2
3
4
5
6

for (int i = 0; i < n; i++) {
    dp[i] = 1;
    if (i > 0 && a[i] > a[i - 1]) {
        dp[i] = dp[i - 1] + 1;
    }
}

这求的是连续段。后面的 [ Rbook: 最长上长子序列] 允许跳过元素，不能直接使用这里的相邻位置转移。

4.3 相同的状态形式，不同的边界含义

不要背成“条件成立就加一，否则归零”。应该先问：当前位置单独拿出来，是否也是合法的一段？

5 CF1948D：先转化，再寻找连续段

题目链接：[ codeforces 1948D: Tandem Repeats?]

这道题给定一个由小写字母和 ? 组成的字符串。每个 ? 可以独立替换为任意小写字母，要求找到最长的一个子串，使它由两个相邻且完全相同的字符串拼接而成；不存在时输出 0。

例如 aabaab 的前半段和后半段都是 aab，因此它是一个长度为 6 的合法重复串。

这里不能直接判断相邻字符是否相同，因为我们要比较的是前后两半的对应位置。

5.1 固定一半的长度，比较位置就确定了

设一半的长度为 $d$。如果整个重复串从 $l$ 开始，需要比较的字符对恰好是：

两字符能够匹配，当且仅当它们相等，或者至少有一个是 ?。

固定 $d$ 后，定义一个概念上的匹配序列：

那么，从 $l$ 开始的长度为 $2d$ 的子串合法，恰好等价于：

也就是说，固定 $d$ 后，只需判断匹配序列中是否存在连续至少 $d$ 个 1。

为什么逐对匹配就能保证问号的替换没有冲突？因为在选定的这两个长度为 $d$ 的半段中，每个字符位置只属于一对。这 $d$ 对可以各自完成替换，不会要求同一个问号同时取两个不同的字母。我们只需完成选中的 $d$ 对，不要求更长匹配段中的所有字符对同时成立。

5.2 用同一个状态解决转化后的问题

固定 $d$，定义：

这与连续正数段的状态形式相同：

这里 $dp[i]$ 数的是连续匹配的字符对数，并不是原字符串中整个重复串的长度。只要出现 $dp[i]\ge d$，就能取最后的 $d$ 对字符，得到长度为 $2d$ 的合法重复串。

5.3 手算固定距离的匹配过程

沿用一个没有问号的例子：

1
2

下标 i：0 1 2 3 4 5 6 7
字符 s：z a a b a a b z

固定 $d=3$：

到 $i=3$ 时，已经连续匹配了 $d=3$ 对：

它们对应前半段 s[1..3] = aab 和后半段 s[4..6] = aab，得到长度为 6 的重复串。

一般地，在位置 $i$ 达到连续 $d$ 对时，取最后 $d$ 对，其左半段起点是 $l=i-d+1$，整个重复串的范围为 $s[l..i+d]$。循环边界 $i+d<n$ 保证右端没有越界。

5.4 恢复对 d 的枚举

固定 $d$ 的 DP 只回答“长度为 $2d$ 的重复串是否存在”。原问题还要求最大长度，所以要枚举 $1\le d\le\lfloor n/2\rfloor$。

从大到小枚举 $d$，第一次找到合法重复串就可以返回：所有更大的候选长度已经检查过了。

如果逐个枚举 $d$ 和起点，再从头检查 $d$ 对字符，总时间最坏为 $O(n^3)$。现在每个 $d$ 只扫描一次，时间降为 $O(n^2)$。

核心转化是固定距离后得到匹配序列；DP 让这个序列上的连续段检查可以共用前一步的结果。

6 为什么可以只保留一个变量？

观察上面的转移，计算 $dp[i]$ 时只需要 $dp[i-1]$，之后也不需要回头查询更早的状态。

因此可以用一个变量 cnt 保存当前连续段的长度。以连续正数段为例：

1
2
3
4
5
6
7
8
9
10

int cnt = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
    if (a[i] > 0) {
        cnt++;
    } else {
        cnt = 0;
    }
    ans = max(ans, cnt);
}

循环不变量是：处理完位置 $i$ 后，cnt 就等于原先的 $dp[i]$，ans 等于前缀最优值 $f[i+1]$。

所以，省掉数组并没有改变状态的含义。时间仍为 $O(n)$，额外空间降为 $O(1)$。

这通常称为滚动变量或 DP 的空间优化。本书目录中的“状态压缩”主要讨论二进制状态表示，与这里省掉历史数组的做法含义不同。

对于 CF1948D，连匹配数组 b 也不必实际保存，扫描时直接比较字符即可。下面的函数只处理一个字符串，返回最长合法重复串的长度；假设已经引入 C++ 标准库并使用 std 命名空间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int longest_tandem(const string &s) {
    int n = s.size();
    for (int d = n / 2; d >= 1; d--) {
        int cnt = 0;  // 每次更换距离，都重新开始计算连续匹配对数
        for (int i = 0; i + d < n; i++) {
            if (s[i] == s[i + d] || s[i] == '?' || s[i + d] == '?') {
                cnt++;
            } else {
                cnt = 0;
            }
            if (cnt >= d) {
                return 2 * d;
            }
        }
    }
    return 0;
}

对长度为 $n$ 的一个字符串，总时间为 $O(n^2)$，除输入字符串外的额外空间为 $O(1)$。

7 哪些问题可以迁移这个思路？

遇到连续区间问题时，可以依次检查：

1. 固定一个结尾后，能否把合法段看成“前一段接上当前元素”？
2. 判断能否延续，需要哪些信息？上一个状态和相邻元素是否足够？
3. 如果不能延续，当前位置应该独立成段，还是连长度为 1 的段都不合法？
4. 最终要求的是某个结尾的答案、全局最大值，还是达到某个长度即可？

这些问题用于设计状态，不能代替对转移的证明。

例如，“区间内最多出现两个不同的数”也要求连续，但只记录末尾合法段的长度通常不够：新元素加入后，还需要知道区间里有哪些数、各出现多少次，才能决定如何调整左边界。“必须以当前位置结尾”可以作为思考起点，却不会自动得到“加一或归零”的转移。

同样，最长相同字符段、最长递增连续段中的每一个较短后缀都合法，所以前一段越长，能延续出的新段也越长；换成别的区间条件时，这一点需要重新检查。

7.1 练习一：失败后保留多少？

求最长的连续非递减段，也就是允许相邻元素相等。

请先写出 $dp[i]$ 的含义，再回答：延续条件是什么？失败时是 0 还是 1？

7.2 练习二：前缀最优值能否延续？

对于序列 [1, 1, 0, 1]，把每个 1 看作合法元素、0 看作不合法元素，分别写出 $dp[0..3]$ 和 $f[0..4]$。

7.3 练习三：匹配一对和匹配一个重复串有什么区别？

CF1948D 中，固定 $d=2$，设字符串为 a?ab。写出匹配序列，判断能否得到长度为 4 的重复串，并给出一种问号替换方式。