o2o电子商务网站/营销策略4p分析怎么写

力扣传送门
这题的dp想法是容易得到的：定义dp[i][j]为数字串s[1~i]且最后一个数字为j位的方案数。那么dp[i-j][k]，1 <= k < j，都是要加到dp[i][j]上的。而dp[i-j][j]只有在s[i-2*j+1~i-j]所表示的数字≤s[i-j+1~i]所表示的数字时，才加到dp[i][j]上。

而dp[i-j][k]，k>j总是没有贡献，因为：

• 非前导0的情况，数字位数更大
• 有前导0的情况是非法的

综上，不妨把dp定义为前缀和，即dp[i][j]为数字串s[1~i]且最后一个数字≤j位的方案数之和。

值得注意的是，为了避免繁杂的分类讨论，我们不妨定义dp[i][j]，i < j <= n等于dp[i][i]。于是我们有如下代码：

  for (let i = 1; i <= n; ++i) {for (let j = 1; j <= i; ++j) {if (s[i - j + 1] !== '0') {if (cmp(i - 2 * j + 1, i - j + 1, j) <= 0)dp[i][j] = (dp[i][j] + dp[i - j][j]) % modelsedp[i][j] = (dp[i][j] + dp[i - j][j - 1]) % mod}dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod}for (let j = i + 1; j <= n; ++j) dp[i][j] = dp[i][j - 1]}return dp[n][n]

这时，我们发现了瓶颈：需要比较两个长度相等的数字串所表示的数字的大小，比较大约n^2次。暴力比较，会导致dp转移的复杂度变为n^3。如何优化？

我们发现，暴力比较过程要找到两个数字串的第一个不相等的位置，这等价于寻找两个子串的lcp（最长公共前缀）。而两个子串的lcp，可以由两个后缀的lcp轻易地得到。因此我们的目标，就是找到预处理出任意两个后缀的lcp。这不就是我们熟知的后缀数组里的height数组吗？

因此我们只需要在n^2*logn的时间内求出height数组。因为我没有后缀数组的倍增模板，所以我直接手打了一个n^2*logn求height数组的模板。

顺便说一句：假如我们缺少可直接cv的模板，那么我们应该在复杂度允许的情况下，选择思考难度最低的做法，这是非常非常重要的竞赛常识（也是非常重要的业务常识）。我付出了血的代价，才对此有了初步的体会！大家千万千万千万要吸取我的失败教训，要保持警惕，不要变成我这种菜鸡！

  const n = s.length, mod = 1e9 + 7s = '0' + slet init = () => {let rk = new Array(n + 5).fill(0)let ht = new Array(n + 5).fill(0)const D = Math.ceil(Math.log2(n + 5))let ST = Array.from({length: D}, () => new Array(n + 5).fill(Infinity))let arr = ['']for (let i = 1; i <= n; ++i) {arr.push(s.substr(i, n - i + 1))}arr.sort()for (let i = 1; i <= n; ++i) rk[n - arr[i].length + 1] = ifor (let i = 2; i <= n; ++i) {let lcp = 0, len = Math.min(arr[i].length, arr[i - 1].length)while (lcp < len && arr[i][lcp] === arr[i - 1][lcp]) ++lcp;ht[i] = lcp}ST[0] = ht.slice()for (let i = 1; i < D; ++i) {for (let j = 1; j <= n - (1 << i) + 1; ++j) {ST[i][j] = Math.min(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))])}}return {rk, ST}}

完整代码

"use strict";var numberOfCombinations = function(s) {const n = s.length, mod = 1e9 + 7s = '0' + slet init = () => {let rk = new Array(n + 5).fill(0)let ht = new Array(n + 5).fill(0)const D = Math.ceil(Math.log2(n + 5))let ST = Array.from({length: D}, () => new Array(n + 5).fill(Infinity))let arr = ['']for (let i = 1; i <= n; ++i) {arr.push(s.substr(i, n - i + 1))}arr.sort()for (let i = 1; i <= n; ++i) rk[n - arr[i].length + 1] = ifor (let i = 2; i <= n; ++i) {let lcp = 0, len = Math.min(arr[i].length, arr[i - 1].length)while (lcp < len && arr[i][lcp] === arr[i - 1][lcp]) ++lcp;ht[i] = lcp}ST[0] = ht.slice()for (let i = 1; i < D; ++i) {for (let j = 1; j <= n - (1 << i) + 1; ++j) {ST[i][j] = Math.min(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))])}}return {rk, ST}}let qry = (l, r) => {if (l > r) [l, r] = [r, l]++lconst d = Math.floor(Math.log2(r - l + 1))return Math.min(ST[d][l], ST[d][r - (1 << d) + 1])}let cmp = (l1, l2, len) => {if (l1 <= 0) return -1let lcp = qry(rk[l1], rk[l2])if (lcp >= len) return 0return s[l1 + lcp] - s[l2 + lcp]}let dp = Array.from({length: n + 5}, () => new Array(n + 5).fill(0))dp[0].fill(1)let {rk, ST} = init()for (let i = 1; i <= n; ++i) {for (let j = 1; j <= i; ++j) {if (s[i - j + 1] !== '0') {if (cmp(i - 2 * j + 1, i - j + 1, j) <= 0)dp[i][j] = (dp[i][j] + dp[i - j][j]) % modelsedp[i][j] = (dp[i][j] + dp[i - j][j - 1]) % mod}dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod}for (let j = i + 1; j <= n; ++j) dp[i][j] = dp[i][j - 1]}return dp[n][n]
};/*
2 0 0 101 4
1 2 2 4 50
*/
let arr = ["327", "094", "0", "9999999999999", "49593","4", "49", "495", "4959", "1145141919810"
]
for(let x of arr) {console.log(numberOfCombinations(x))
}