#820 Div.3 G. Cut Substrings dp*

Problem G
dp

题意

有两个字符串 $s,t$ ，每次操作可以在 $s$ 中选择一个等于 $t$ 的子串。将这部分每个字符变为"." ，求最少进行多少次操作可以使得 $s$ 中没有 $t$ ，并求出该次数下的不同方案数。例如 s = "abababacababa"，t = "aba" ，可以替换 3、9,也可以替换3、11位置，分别得到 "ab...bac...ba","ab...bacab...",所以最少操作次数是2，不同方案数也是2。

思路

回忆求最长上升子序列及其数量的方法，用 $f[i]$ 表示到 第 $i$ 个数为止最长上升子序列的长度， $tot[i]$ 表示对应的方案数。则可通过如下代码在 $O(n^2)$ 求解。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
        if (a[j] < a[i]) {
            if (f[i] < f[j] + 1) {
                f[i] = f[j] + 1;
                tot[i] = tot[j];
            }
            else if (f[i] == f[j] + 1) {
                tot[i] = (tot[i] + tot[j]) % P;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

对于这道题目，先将 $s$ 中所有等于 $t$ 的子串筛出来，并将每个子串的末位存入 vector v 。可以按照类似的方法求解。

但需要明确什么状态下无法进行 $f[i]=f[j]+1$ 的转移 。

在上图中，设绿条是我们目前的 $i$ ，紫条是我们目前的 $j$ ，上述两种情况都无法进行转移，我们只要在转移的过程中排除这两种情况就可以了。时间复杂度 $O(n^3)$

	f[0] = 0;
    tot[0] = 1;
    bool fg = 1;
    for(int i = 1; i < v.size(); i++) {
        for(int j = i - 1; j >= 0; j--) {
            if(v[i] - v[j] < m) continue; //Case 1
            fg = 1;
            for(int k = j + 1; k < i; k++) {
                if(v[i] - v[k] >= m && v[k] - v[j] >= m) {
                    fg = 0;  //Case 2
                    break;
                }
            }
            if(!fg) break;
            if(f[i] > f[j] + 1) {
                f[i] = f[j] + 1;
                tot[i] = tot[j];
            }
            else if(f[i] == f[j] + 1){
                tot[i] = (tot[i] + tot[j]) % P;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注意最终的方案统计，需要考虑所有和最后一个块有重叠的块。

代码

int f[maxn];//到第i个t串所需要删的最少个数
int tot[maxn];//到第i个t串所需要删的最少个数对应的方案数
void solve() {
    string s, t;
    cin >> s >> t;
    int n = s.length();
    int m = t.length();
    s = ' ' + s;
    for(int i = 1; i <= n; i++) {
        tot[i] = 0;
        f[i] = INF;
    }
    vector<int> v;
    v.pb(0);
    for(int i = 1; i + m - 1 <= n; i++) {
        if(s.substr(i, m) == t) v.pb(i + m - 1);
    }
    f[0] = 0;
    tot[0] = 1;
    bool fg = 1;
    for(int i = 1; i < v.size(); i++) {
        for(int j = i - 1; j >= 0; j--) {
            if(v[i] - v[j] < m) continue; //例如ababa
            fg = 1;
            for(int k = j + 1; k < i; k++) {
                if(v[i] - v[k] >= m && v[k] - v[j] >= m) {
                    fg = 0;//例如aba aba aba
                    break;
                }
            }
            if(!fg) break;
            if(f[i] > f[j] + 1) {
                f[i] = f[j] + 1;
                tot[i] = tot[j];
            }
            else if(f[i] == f[j] + 1){
                tot[i] = (tot[i] + tot[j]) % P;
            }
        }
    }
    int la = *v.rbegin();
    int ans1 = INF, ans2 = 0;
    for(int i = v.size() - 1; i >= 0; i--) {
        if(la - v[i] < m) {
            chmin(ans1, f[i]);
        }
        else {
            break;
        }
    }
    for(int i = v.size() - 1; i >= 0; i--) {
        if(la - v[i] < m) {
            if(f[i] == ans1) {
                ans2 = (ans2 + tot[i]) % P;
            }
        }
        else {
            break;
        }
    }
    cout << ans1 << ' ' << ans2 << endl;
}
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62