原题呈现

题目描述#

给定两个长度均为 $n$ 的字符串 $S, T$ ，它们都只包含小写英文字母．

另外给定 $m$ 条转换规则，第 $i$ 条规则由三个量组成：

字符串 $A_i$
字符串 $B_i$
代价 $C_i$

并且保证字符串 $A_i$ 与 $B_i$ 的长度相同， $C_i$ 是正整数．

一次操作中，你可以选择当前字符串中的一个区间 $[l, r]$ ，若该区间对应的子串恰好等于某个 $A_i$ ，则可以花费 $C_i$ 的代价，将这一段替换为 $B_i$ ．

你可以进行任意多次操作，但所有操作所选择的区间必须满足下面条件之一：

两次操作所选区间完全相同；
两次操作所选区间没有公共位置．

也就是说，若两次操作作用在不同区间上，则这两个区间不能有任何重叠；若有重叠，则它们必须是同一个区间．

请你求出将字符串 $S$ 变为字符串 $T$ 的最小总代价．若无法完成转换，输出 $-1$ ．

输入格式#

第一行一个字符串 $S$ ．第二行一个字符串 $T$ ．第三行一个整数 $m$ ，表示转换规则的条数．接下来 $m$ 行，每行输入两个字符串 $A_i, B_i$ 和一个整数 $C_i$ ，表示一条规则．

输出格式#

输出一个整数，表示将 $S$ 转换为 $T$ 的最小总代价．如果无解，输出 $-1$ ．

样例#

样例 1#

输入

1
abcd
2
acbe
3
6
4
a b 2
5
b c 5
6
c b 5
7
c e 1
8
e b 2
9
d e 20

输出

1
28

样例 2#

输入

1
abcdefgh
2
acdeeghh
3
3
4
bcd cde 1
5
fgh thh 3
6
thh ghh 5

输出

1
9

样例 3#

输入

1
abcdefgh
2
addddddd
3
2
4
bcd ddd 100
5
defgh ddddd 1578

输出

1
-1

样例解释#

样例 1#

一种最优方案如下：

把位置 $2$ 上的 b 变成 c，代价 $5$ ；
把位置 $3$ 上的 c 变成 e，代价 $1$ ；
再把位置 $3$ 上的 e 变成 b，代价 $2$ ；
把位置 $4$ 上的 d 变成 e，代价 $20$ ．

总代价为 $5 + 1 + 2 + 20 = 28$ ．注意第三步与第二步作用在同一个区间，因此是允许的．

样例 2#

可以按如下方式转换：

将区间 $[2,4]$ 的 bcd 变为 cde，代价 $1$ ；
将区间 $[6,8]$ 的 fgh 变为 thh，代价 $3$ ；
再将区间 $[6,8]$ 的 thh 变为 ghh，代价 $5$ ．

前一次和后两次操作分别作用在两个互不相交的区间上，因此合法；后两次操作作用在同一个区间上，也合法．

总代价为 $1 + 3 + 5 = 9$ ．这也是最小代价．

样例 3#

若先把区间 $[2,4]$ 的 bcd 变成 ddd，那么之后若想再处理区间 $[4,8]$ ，这两个区间会在位置 $4$ 发生重叠，但它们并不是同一个区间，因此不合法．反过来，若先处理区间 $[4,8]$ ，再处理区间 $[2,4]$ ，同样会产生非法重叠．因此无论怎样都无法得到目标串，答案为 $-1$ ．

数据范围#

对于所有数据，满足：

$1 \le n \le 50000$
$1 \le m \le 100$
$1 \le |A_i| = |B_i| \le n$
$1 \le C_i \le 10^5$
字符串仅由小写字母组成．

测试点编号	$n \le$	$m \le$	特殊限制
1,2	$10$	$10$	-
3,4,5	$1000$	$100$	所有规则长度为 $1$
6,7,8	$1000$	$100$	所有规则长度 $\le 50$
9,10	$50000$	$100$	所有规则长度为 $1$
11~14	$50000$	$100$	所有规则长度 $\le 50$
15~20	$50000$	$100$	-

观察所谓的转换规则：给定一个起始字符串，一个终点字符串，和一个将起始字符串转换为终点字符串的权值，可以将其想象成一条单项边，使用哈希将两个字符串离散成两个数字，并使用 map 映射到点的编号．

因此，对于所有的转换规则，可以将其看作是一张图，只需要在图上跑一边 floyd，就可以在 $O(1)$ 得知两个字符串之间的权值，floyd 时间复杂度 $O(m^3)$ ．

紧接着，观察这个 $n$ 的范围，可以使用 dp，定义 dp[i] 表示 $s$ 和 $t$ 的前 $i$ 个字符相等（即：s[0..i-1] = t[0..i-1]）所需要的代价，有初始状态：

1
dp[0] = 0;

有转移方程：

dp[i] = \min^{i}_{len=1} dp[i-len] + cost(i-len+1, i)

其中， $cost(l,r)$ 指通过一次变换操作将 $s[l..r]$ 变为 $t[l..r]$ 所需要的代价，可以先预处理出 $s$ 和 $t$ 的哈希，再将两者进行子串哈希为数字 $hl$ 和 $hr$ ，复杂度 $O(1)$ ，再通过 map 找到点的编号 $a$ 和 $b$ ，最后查询 floyd 得到的 dis 数组， $cost(l,r)=dis[a][b]$ ．当然，如果查询不到 $a$ 和 $b$ （ $map[hl]$ 或 $map[lr]$ 为 0），或者说 $a$ 到 $b$ 没有连边，这个转移方程就不成立．

最终状态：dp[s.size()]．

你会发现，这个 dp 是 $O(n^2)$ 的，怎么优化呢？不难发现，一共只有 $m$ 条规则，每条规则只有一个起始字符串，也就是说最多只有 $m$ 个起始字符串，也就是说，这些字符串的长度最多只有 $m$ 种，因此，在上述转换方程中， $len$ 不需要从 $1$ 枚举到 $i$ ，只需要遍历所有字符串长度组成的集合 len_set（举个例子，看测试点 3~5，所有的起始字符串长度都是 1，因此 len_set 中只有 1，len 也只需要取到 1，取到别的是浪费时间的操作），时间复杂度 $O(nm)$ ．

看着不错，交一发试试．恭喜你，被卡常了．

这里有一些卡常小技巧：

能不用 long long 就不用．
使用快读快写．
少用 STL 的迭代器，对于 set 和 map 可以转成 vector 之后使用下标读写．
减少 vector 申请空间的次数．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int BASE = 128;
4
const int N = 50005;
5
const int M = 2 * 105;
6
const int MOD = 1e9 + 7;
7
const int INF = 0x3f3f3f3f;
8
string s, t;
9
int m, dis[M][M], cnt;
10
map<int, int> g;
11
set<int> len_set;
12
int dp[N]; // dp[i] 表示前 i 个字符相等的代价
13
int sh[N], th[N];
14
int p[N];
15

16
// 哈希函数，针对字符串
17
int hs(string &str) {
18
    int h = 0;
19
    for (int i = 1; i <= str.size(); i++) {
20
        (h = 1ll * h * BASE % MOD + str[i - 1]) %= MOD;
21
    }
22
    return h % MOD;
23
}
24

25
// 哈希函数，针对子串
26
int hs(int *h, int l, int r) {
27
    return (h[r] - (1ll * h[l - 1] * p[r - l + 1] % MOD) + MOD) % MOD;
28
}
29

30
// 计算[l,r]的花费，1-based
31
int cost(int l, int r) {
32
    int a = g[hs(sh, l, r)];
33
    int b = g[hs(th, l, r)];
34
    if (a == 0 || b == 0)
35
        return INF;
36
    return dis[a][b];
37
}
38

39
signed main() {
40
    freopen("string.in", "r", stdin);
41
    freopen("string.out", "w", stdout);
42
    ios::sync_with_stdio(false);
43
    cin.tie(0);
44
    cout.tie(0);
45
    cin >> s >> t >> m;
46
    memset(dis, 0x3f, sizeof(dis));
47
    // 预处理哈希
48
    p[0] = 1;
49
    for (int i = 1; i <= s.size(); i++) {
50
        sh[i] = (1ll * sh[i - 1] * BASE + s[i - 1]) % MOD;
51
    }
52
    for (int i = 1; i <= t.size(); i++) {
53
        th[i] = (1ll * th[i - 1] * BASE + t[i - 1]) % MOD;
54
        p[i] = 1ll * p[i - 1] * BASE % MOD;
55
    }
56
    // 建图
57
    for (int i = 1; i <= m; i++) {
58
        string a, b;
59
        int c;
60
        cin >> a >> b >> c;
61
        len_set.insert(a.size());
62
        int ha = hs(a), hb = hs(b);
63
        if (g[ha] == 0)
64
            g[ha] = ++cnt;
65
        if (g[hb] == 0)
66
            g[hb] = ++cnt;
67
        int x = g[ha], y = g[hb];
68
        dis[x][y] = min(dis[x][y], c);
69
    }
70
    // floyd
71
    for (int i = 1; i <= cnt; i++) {
72
        dis[i][i] = 0;
73
    }
74
    for (int k = 1; k <= cnt; k++) {
75
        for (int i = 1; i <= cnt; i++) {
76
            for (int j = 1; j <= cnt; j++) {
77
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
78
            }
79
        }
80
    }
81
    vector<int> len;
82
    for (auto i : len_set)
83
        len.push_back(i);
84
    // 开始 DP
85
    memset(dp, 0x3f, sizeof(dp));
86
    dp[0] = 0;
87
    for (int i = 1; i <= s.size(); i++) {
88
        if (s[i - 1] == t[i - 1]) {
89
            dp[i] = min(dp[i], dp[i - 1]);
90
        }
91
        for (int j : len) {
92
            if (i - j >= 0) {
93
                int c = cost(i - j + 1, i);
94
                if (c >= INF)
95
                    continue;
96
                dp[i] = min(dp[i], dp[i - j] + c);
97
            }
98
        }
99
    }
100
    if (dp[s.size()] < INF)
101
        cout << dp[s.size()];
102
    else {
103
        cout << -1;
104
    }
105
}

字符串问题可以通过哈希 + map 离散化转换为数字问题．

音乐

音乐

题目描述#

输入格式#

输出格式#

样例#

样例 1#

样例 2#

样例 3#

样例解释#

样例 1#

样例 2#

样例 3#

数据范围#

文章分享

音乐

安吉D3-T4

题目描述#

输入格式#

输出格式#

样例#

样例 1#

样例 2#

样例 3#

样例解释#

样例 1#

样例 2#

样例 3#

数据范围#

文章分享