- 题目链接：小Z的笔记
题目思路：dp，二维不会想，我们直接来一维，我们用dp[i]来表示第i位最少要擦掉几个字母，对于第j位，假设j和i可以相邻，那么状态转移方程明显为
1
dp[i] = min(dp[i], dp[j] - j + i - 1);
也就是说，我们要把j+1 —— i-1删掉，但这样的时间复杂度为θ(n^2)， 只能过30%的数据，我们要对此进行优化。
- 优化：我们发现，对于每一次状态转移，我们要找的是最小的dp[j]，我们可以用一个数组单独来存最小的的dp[j],我们用数组f[i]表示字母i最小的dp[j]-j，这样时间复杂度就降为了θ(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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;
int sc() {
int xx = 0, ff = 1; char cch = gc;
while (cch < '0' || cch > '9') {
if (cch == '-') ff = -1; cch = gc;
}
while (cch >= '0'&& cch <= '9') {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
int n, m;
bool pd[30][30];
char s[Maxn];
int f[Maxn], dp[Maxn];
int main() {
// freopen("note.in", "r", stdin);
// freopen("note.out", "w", stdout);
n = sc();
scanf("%s", s + 1);
m = sc();
for(int i = 1; i <= m; i++) {
char c[2];
cin >> c[0] >> c[1];
c[0] = c[0] - 'a' + 1;
c[1] = c[1] - 'a' + 1;
int aa = c[0]; int bb = c[1];
pd[aa][bb] = pd[bb][aa] = 1;
}
memset(dp, 0x7f, sizeof(dp));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 26; j++)
if(! pd[s[i] - 'a' +1][j])
dp[i] = min(dp[i], f[j] + i - 1);
f[s[i] - 'a' + 1] = min(f[s[i] - 'a' + 1], dp[i] - i);
}
printf("%d\n", dp[n]);
return 0;
}