AT3741 String Problem

皎月半洒花

2020-04-28 08:18:49

Solution

兔这么可爱,最喜欢兔了,所以就要跟着兔做题鸭 ~~xht:兔是我的我的~~ 以上是扯淡。看到兔发的讨论就来秒一秒,结果真秒了( 大家别再抄 std 或者兔的代码啦,这样一点也不帅。还是自己想想比较好吧。 ____ 根据第一个样例不难想到,加 B 和删 A 这两个操作本质上没有任何关系,所以可以分开做。那么可以知道,如果只看加 B 的操作,那么需要 $t$ 在 $s$ 加完 B 之后,是 $s$ 的某个子序列。这个可以直接仿照 LCS 的 dp,$f_{i,j}$ 表示最多匹配多少位。xxs转移不再赘述。 考虑接下来是删 A。那么如果确定了 $t$ 是 $s$ 的子序列,那么就只需要知道 $s$ 中是否有奇怪的、没法被删的多余元素。于是再维护一个 $g_{i,j}$ 表示若想要 $s_i$ 和 $t_j$ 匹配上,最少需要向 $s$ 内添加多少个 B。之后就只需要比较一下是否 $s$ 比 $t$ 只是多一堆 A 即可。 ~~应该从 0 开始枚举,挂了一发;改成 0 之后越界了,于是又挂了一发,我太难了~~ ```cpp int n, m ; int sa, ta ; int f[N][N] ; int g[N][N] ; char s[N], t[N] ; int main(){ cin >> (s + 1) >> (t + 1) ; n = strlen(s + 1), m = strlen(t + 1) ; s[0] = '#' ; memset(g, 63, sizeof(g)) ; g[0][0] = g[1][0] = g[0][1] = 0 ; for (int i = 0 ; i <= n ; ++ i) for (int j = 1 ; j <= m ; ++ j){ if (f[i - 1][j] > f[i][j] || (f[i - 1][j] == f[i][j] && g[i - 1][j] < g[i][j])) g[i][j] = g[i - 1][j], f[i][j] = f[i - 1][j] ; if (f[i][j - 1] > f[i][j] || (f[i][j - 1] == f[i][j] && g[i][j - 1] < g[i][j])) g[i][j] = g[i][j - 1], f[i][j] = f[i][j - 1] ; if (t[j] == 'B'){ int w = f[i][j - 1] + 1 ; if (w > f[i][j] || (w == f[i][j] && g[i][j - 1] + 1 < g[i][j])) g[i][j] = g[i][j - 1] + 1, f[i][j] = f[i][j - 1] + 1 ; } if (s[i] == t[j]){ int w = f[i - 1][j - 1] + 1 ; if (w > f[i][j] || (w == f[i][j] && g[i - 1][j - 1] < g[i][j])) g[i][j] = g[i - 1][j - 1], f[i][j] = f[i - 1][j - 1] + 1 ; } // printf("%d %d %d\n", i, j, f[i][j]) ; } // cout << f[n][m] << '\n' ; // cout << g[n][m] << '\n' ; if (f[n][m] < m) return puts("NO"), 0 ; for (int i = 1 ; i <= n ; ++ i) sa += s[i] == 'A' ; for (int i = 1 ; i <= m ; ++ i) ta += t[i] == 'A' ; if (sa - ta != n + g[n][m] - m) return puts("NO"), 0 ; else return puts("YES"), 0 ; } ```