1416. 恢复数组

发表于 分类于 阅读次数： Waline： 本文字数： 241 阅读时长 ≈ 1 分钟

考点

  • 划分DP

思路

划分DP裸题，不再赘述

需要注意的是，k最大只有10位，枚举的时候子数组最大长度保持10位以内即可，long long不会溢出

倒序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  static const int maxn = 1e5 + 5, mod = 1e9 + 7;
  int numberOfArrays(string s, int k) {
    int n = s.size(), bit = to_string(k).size();
    s = "0" + s;
    long long f[maxn];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
      long long sum = 0, p = 1;
      for (int j = i; j >= max(1, i + 1 - bit); --j) {
        sum += p * (s[j] - '0');
        if (sum > k) break;
        if (s[j] - '0' != 0) f[i] = (f[i] + f[j - 1]) % mod;
        p *= 10;
      }
    }
    return f[n];
  }
};

正序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  static const int maxn = 1e5 + 5, mod = 1e9 + 7;
  int numberOfArrays(string s, int k) {
    int n = s.size(), bit = to_string(k).size();
    s = "0" + s;
    long long f[maxn];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
      if (s[i + 1] == '0') continue;
      long long sum = 0;
      for (int j = i + 1; j <= min(n, bit + i); ++j) {
        sum = sum * 10 + (s[j] - '0');
        if (sum > k) break;
        f[j] = (f[j] + f[i]) % mod;
      }
    }
    return f[n];
  }
};