P8256 [NOI Online 2022 入门组] 字符串 题解
PosVII
·
·
题解
前言
我已经很久没有写题解了，有点小激动。
同学认为我的思路晦涩难懂，我很伤心。
思路
首先我们要确定，每次加进去的字符是在一开始就决定了它的结果：被从 R 左边删除（称为 l）、被从 R 右边删除（称为 r）、成为 T 的一部分（称为 o）。由于加字符只能从后面加，所以当我们决定它要成为 T 的一部分时，它在 T 中所属的下标也唯一确定了。
因为 S 的操作确定，字符串 R 的长度也一定确定。
对于字符串 R，它的样子肯定长这样：
l l l l o o o o r r r r
解释一下为什么 l 和 r 中没有零散的 o，很简单，因为你要把左边该删掉的一定要连续地删掉，不能把不该删的删了，右边的同理。确定了 R 的形态，动态规划就比较好想了。
设 dp_{i,j,k} 是当执行到第 i 个操作时，左边有 j 个字符要被删掉，右边有 k 个字符要被删掉时方案数，由于此时 R 的长度一定，中间 o 的数量也确定了。
设此时 R 长度为 len，状态转移就是：
当 s_{i} 是 '-' 时：
当 $s_{i}$ 非 '-' 时：
$dp_{i,j,k} = dp_{i-1,j,k} + dp_{i-1,j,k-1}$（只要此时后面有必须要删的，就意味着新加的也要在后面被删掉，即：$1 \leq k$）。
$dp_{i,j,k} = dp_{i,j,k} + dp_{i-1,j,k}$（可以加在后面且匹配，即：$k = 0$ & $t_{len-j} = s_{i}$）。
$dp_{i,j,k} = dp_{i,j,k} + dp_{i-1,j-1,k}$（**重中之重**，当全都是 l 时，加在后边也可以在左边删除）。
时间复杂度 $O(n^3)$，和他人不同。
**code**
------------
```
#include<bits/stdc++.h>
using namespace std;
template<typename G>inline void read(G&x) {x=0;G f=1;char ch=getchar();while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();if(ch=='-') {f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+(ch^48);ch=getchar();}x*=f;}
const int MAXN=405,p=1e9+7;
int T,n,m,tot,dp[MAXN][MAXN][MAXN];
char s[MAXN],t[MAXN];
int main() {
read(T);
while(T--) {
read(n),read(m);
cin>>(s+1)>>(t+1);
tot=0;
for(int i=1;i<=n;++i) {
if(s[i]=='-') ++tot;
}
if(n-tot*2!=m) {
puts("0");
continue;
}
int len=0;
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
for(int i=1;i<=n;++i) {
if(s[i]=='-') --len;
else ++len;
for(int j=0;j<=tot;++j) {
for(int k=0;k<=tot;++k) {
if(s[i]=='-') {
dp[i][j][k]=(dp[i-1][j+1][k]+dp[i-1][j][k+1])%p;
}
else {
if(k>0) dp[i][j][k]=dp[i-1][j][k-1];
else if(t[len-j]==s[i]) dp[i][j][k]=dp[i-1][j][k];
if(len==j) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k])%p;
}
}
}
}
printf("%d\n",dp[n][0][0]);
}
return 0;
}
```