自动搬运

查看原文

来自洛谷，原作者为

	PosVII OI(2021.3-2025.3)

搬运于2025-08-24 22:37:24，当前版本为作者最后更新于2022-04-02 18:12:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

我已经很久没有写题解了，有点小激动。

同学认为我的思路晦涩难懂，我很伤心。

思路

首先我们要确定，每次加进去的字符是在一开始就决定了它的结果：被从 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}$ 是 '-' 时：

$dp_{i,j,k} = dp_{i-1,j+1,k} + dp_{i-1,j,k+1}$（此时选择删左边或删右边）。

当 $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;
}