题解 P2187 【小Z的笔记】

· · 题解

$\ \ \ \ \ \ \ $定义 $dp_i$ 为前 $i$ 个字符中最少需要删除的字符数量。 $\ \ \ \ \ \ \ $如果 $j$ 字符与则 $i$ 字符可以相邻 $(j < i)$, 则 $dp_i$ 可以由删除 $(j + 1)$ ~ $(i - 1)$得到 $\ \ \ \ \ \ \ $即： $\ \ \ \ \ \ \ $ $ dp_i=\min \{{dp_{i},dp_j+(i-j-1)\}}

codeTLE:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
bool vis[105][105];
char s[100005], ch[5];
int dp[100005];
int main () {
    int n;
    scanf ("%d %s", &n, s + 1);
    int m;
    scanf ("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf ("%s", ch + 1);
        vis[ch[1]-'a'+1][ch[2]-'a'+1] = vis[ch[2]-'a'+1][ch[1]-'a'+1] = 1;//双向
    }
    memset (dp, 0x3f, sizeof dp);//因为dp取最小值，所以我们初始化时要给dp附上最大值  
    dp[0] = 0;
    s[0] = 'a' - 1;//防止越界
    for (int i = 1; i <= n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (vis[s[i]-'a'+1][s[j]-'a'+1] == 0) {
                dp[i] = min (dp[i], dp[j] + (i - j - 1));//dp[j] 的值加上删除 i - 1 到 j + 1 的花费
            }
        }
    }
    printf ("%d", dp[n]);
    return 0;
}
$\ \ \ \ \ \ \ $ 所以我们要进行以下优化 $\ \ \ \ \ \ \ $ 考虑到输入为 $26$ 个小写字母，我们可以用一个数组 $p$ 来记录之前的值 $\ \ \ \ \ \ \ $ $p_i$ 表示最小的 $dp_j - j$ $(s_j == i)$ ($i$ 与 $s_j$ 都是字母) $\ \ \ \ \ \ \ $ 通过 $dp$ 式转移 $\ \ \ \ \ \ \ $ $ dp_i=\min \{{dp_{i},dp_j+(i-j-1)\}}$ 变为 $\ \ \ \ \ \ \ $ $ dp_i=\min \{{dp_{i},p_j + i - 1\}} ---- ## codeAC: ```cpp #include <cstdio> #include <cstring> #include <algorithm> using namespace std; bool vis[105][105]; char s[100005], ch[5]; int dp[100005]; int p[105]; int main () { int n; scanf ("%d %s", &n, s + 1); int m; scanf ("%d", &m); for (int i = 1; i <= m; i++) { scanf ("%s", ch + 1); vis[ch[1]-'a'+1][ch[2]-'a'+1] = vis[ch[2]-'a'+1][ch[1]-'a'+1] = 1; } memset (dp, 0x3f, sizeof dp); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= 26; j++) if (vis[s[i]-'a'+1][j] == 0) dp[i] = min (dp[i], p[j] + i - 1); p[s[i]-'a'+1] = min (p[s[i]-'a'+1], dp[i] - i); } printf ("%d", dp[n]); return 0; } ``` 时间复杂度 O ($26 * n$)