AT3741 String Problem
皎月半洒花
2020-04-28 08:18:49
兔这么可爱,最喜欢兔了,所以就要跟着兔做题鸭
~~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 ;
}
```