2478. 完美分割的方案数

发表于 分类于 阅读次数： Waline： 本文字数： 1.6k 阅读时长 ≈ 5 分钟

考点

  • 划分DP
  • 双指针
  • 区间长度限制下的剪枝

思路

0. 下标体系与记号约定

  • 字符串真实存储：s[0..n-1]（C++ 数组 0 下标）。

  • 逻辑上用「前缀长度」做 DP 下标：

    • i 表示前 i 个字符（对应实际下标 [0 .. i-1]）。
    • f[j][i] 表示：前 i 个字符被划分成 j 段的方案数，且第 j 段的结尾就在位置 i。

  • 一个切分点在逻辑上记作 l，含义是：

    前一段结尾在位置 l（对应真实字符下标 l-1）， 下一段从 l+1 开始。

    特别地，l = 0 表示“在串最左边之前切一刀”，即第一段从 1（真实下标 0）开始。

1. 子串结构与“割点”条件

一段合法的漂亮子串是一个区间： \[ [l+1,\, i] \quad (\text{逻辑下标}) \] 对应真实字符下标区间： \[ [\,l,\, i-1\,]. \] 要成为一个漂亮子串，必须满足：

  1. 段首是质数数字： \[ s[l] \text{ 是质数数字} \quad (\text{当 } l \ge 1) \] 若 l = 0，意味着从字符串开头开始，质数条件由整体剪枝保证。

  2. 段尾是非质数数字： \[ s[i-1] \text{ 是非质数数字}. \]

  3. 段长至少为 minLength： \[ i - (l+1) + 1 = i - l \ge L, \quad L = \text{minLength}. \]

因此，“在 l 和 l+1 之间切一刀”是合法割点，当且仅当：

  • l == 0，表示第一段从开头开始，或

  • l ≥ 1 且 \[ s[l-1]\ \text{非质数},\quad s[l]\ \text{质数}. \]

这正是代码里的判断：

1
if (l == 0 || !judge(s[l - 1]) && judge(s[l]))

总结：

l 是前一段结尾的前缀长度； 若 l 是合法割点，则下一段可以从 l+1 开始。

2. DP 状态定义与边界

状态定义： \[ f[j][i] = \text{前 } i \text{ 个字符划成 } j \text{ 段，且第 } j \text{ 段结尾为 } i \text{ 的方案数}. \] 初始条件： \[ f[0][0] = 1,\quad f[0][i] = 0\ (i > 0). \] 剪枝条件（在代码最前面做的）：

  • 开头必须是质数数字；
  • 结尾必须是非质数数字；
  • 总长度必须满足 \(n \ge kL\)。

3. 朴素转移：从“前一段结尾 l”枚举

考虑第 j 段结尾在位置 i，这段是： \[ [l+1,\, i] \quad (\text{逻辑前缀长度}). \] 那么前 j-1 段必须恰好在位置 l 结束，转移自然是： \[ f[j][i] = \sum_{\substack{ \text{割点 } l \text{ 合法}\\ i - l \ge L }} f[j-1][l]. \] 其中“割点 l 合法”就是上面说的两种情况：

  • l == 0，或
  • l ≥ 1 且 !prime(s[l-1]) && prime(s[l])。

同时，对 i 也有条件：

  1. 这段的尾必须非质数数字：!prime(s[i-1])。

  2. 必须给前后的段预留足够长度：

    • 前 j 段至少占 jL，所以 \[ i \ge jL. \]

    • 剩余后缀要容纳 (k-j) 段，每段至少 L，长度 n - i，所以 \[ n - i \ge (k-j)L. \]

这两点在的代码对应：

1
2
3
4
5
6
for (int i = j * minLength; 
     i <= n - (k - j) * minLength; 
     ++i) {
  if (judge(s[i - 1])) continue; // 尾必须非质数
  ...
}

4. 枚举 l 的区间与初始 l 的选择

对于给定的 j 和 i，合法的前一段结尾 l 满足：

  1. 长度条件： \[ i-l \ge L \quad\Longleftrightarrow\quad l \le i-L. \]

  2. 前 j-1 段至少占 (j-1)L 个字符，所以末尾位置 l 至少为： \[ l \ge (j-1)L. \]

因此，合法的 l 区间是： \[ l \in [\, (j-1)L,\ i-L\,]. \] 这就是初始化 l 的理由：

1
int l = (j - 1) * minLength;

配合内层双指针：

1
2
3
4
5
6
while (i - l >= minLength) {
  // 此时 l 在 [ (j-1)L, i-L ]
  if (l == 0 || !judge(s[l - 1]) && judge(s[l]))
    sum = (sum + f[j - 1][l]) % mod;
  ++l;
}

每次 i 增大，l 会尽可能向右推，直到 i-l < L 停止。 整个过程中，l 单调不减，每个值最多被处理一次，典型双指针。

5. 双指针中的 sum 含义

对固定的 j，维护了一个变量：

1
long long sum = 0;

每当 i 增大时，通过 while (i - l >= L) 不断推进 l，并对每一个新的、合法的 l 做：

1
2
if (l == 0 || !judge(s[l - 1]) && judge(s[l]))
  sum = (sum + f[j - 1][l]) % mod;

因此，在处理完某个 i 的 while 循环后： \[ \text{sum} = \sum_{\substack{ l\in[(j-1)L,\,i-L]\\ l\ \text{是合法割点} }} f[j-1][l]. \] 正好就是朴素转移中那一大坨求和的结果。

所以对于当前的 i，只需要：

1
f[j][i] = sum;

（前提 s[i-1] 是非质数，且 i 本身在循环边界内；这两点已由外层 for 和 continue 保障。）

也就是说，用一个随 i 单调右移的 l 指针 + 累加和 sum，实现了： \[ f[j][i] = \sum_{\substack{ (j-1)L \le l \le i-L\\ l\ \text{是合法割点} }} f[j-1][l] \] 的 \(O(1)\) 时间转移。

6. 各层边界条件的统一检查

整体逻辑对应如下数学约束：

  1. 全局剪枝：

    • 首字符质数，尾字符非质数；
    • 总长 \(n \ge kL\)。

  2. 外层 j： \[ j = 1,2,\dots,k. \]

  3. 对固定的 j，右端点 i 的枚举区间： \[ i \in [\, jL,\ n - (k-j)L\,], \] 即前缀能放下 j 段，后缀能放下剩余段。

  4. i 作为段结尾的合法性： \[ s[i-1] \text{ 必须为非质数}. \]

  5. 内层双指针 l 的含义与区间：

    • l 是前一段的结尾位置（前缀长度）；

    • 合法区间： \[ l \in [\, (j-1)L,\ i-L\,]; \]

    • 且 l 是合法割点： \[ l=0 \quad \text{或} \quad (!\text{prime}(s[l-1]) \land \text{prime}(s[l])). \]

  6. 对每个 i： \[ f[j][i] = \text{sum} \] 即所有上述合法 l 的 f[j-1][l] 之和。

  7. 最终答案： \[ \text{answer} = f[k][n]. \]

AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  const int mod = 1e9 + 7;
  bool judge(char& x) { return x == '2' || x == '3' || x == '5' || x == '7'; }
  int beautifulPartitions(string s, int k, int minLength) {
    // 剪枝
    if (!judge(s[0]) || judge(s.back()) || s.size() < k * minLength) return 0;
    // DP
    int n = s.size(), f[1005][1005];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int j = 1; j <= k; ++j) {
      long long sum = 0;
      int l = (j - 1) * minLength;
      for (int i = j * minLength; i <= n - (k - j) * minLength; ++i) {
        if (judge(s[i - 1])) continue;
        while (i - l >= minLength) {
          if (l == 0 || !judge(s[l - 1]) && judge(s[l]))
            sum = (sum + f[j - 1][l]) % mod;
          ++l;
        }
        f[j][i] = sum;
      }
    }
    return f[k][n];
  }
};

滚动数组减少常数开销：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  const int mod = 1e9 + 7;
  bool judge(char& x) { return x == '2' || x == '3' || x == '5' || x == '7'; }
  int beautifulPartitions(string s, int k, int minLength) {
    // 剪枝
    if (!judge(s[0]) || judge(s.back()) || s.size() < k * minLength) return 0;
    // DP
    int n = s.size(), f[2][1005];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int j = 1; j <= k; ++j) {
      long long sum = 0;
      int l = (j - 1) * minLength;
      for (int i = j * minLength; i <= n - (k - j) * minLength; ++i) {
        if (judge(s[i - 1])) continue;
        while (i - l >= minLength) {
          if (l == 0 || !judge(s[l - 1]) && judge(s[l]))
            sum = (sum + f[j - 1 & 1][l]) % mod;
          ++l;
        }
        f[j & 1][i] = sum;
      }
    }
    return f[k & 1][n];
  }
};