题目大意：给你三个串a,b,c，问a和b是不是恰好能组成c，也就是a,b是不是c的两个互补的子序列。
根据题意就可以知道对于c的第一个就应该是a第一个或者b的第一个，如果第一个是a的第一个，那么c的第二个就应该是a的第二个或者是b的第一个，反之也是一样的。那么我们定义dp[i][j]就是a串匹配到i位置，b串匹配到j位置的合理性，那么dp[i][j]就由dp[i-1][j]和dp[i][j-1]推过来，a串匹配到i位置，b串匹配到j位置，那么c串就匹配到了i+j位置，然后判断是否匹配即可。
#include<cstdio>
#include<cstring>
const int N=;
bool dp[N][N];
char a[N],b[N],c[N];
int main()
{
while(~scanf("%s",a+))
{
scanf("%s",b+);
scanf("%s",c+);
int lena=strlen(a+),lenb=strlen(b+),lenc=strlen(c+);
if(lena+lenb!=lenc)//c的长度肯定得是等于a和b之和
{
printf("No\n");
continue;
}
for(int i=;i<=lena;i++)
for(int j=;j<=lenb;j++)
dp[i][j]=false;
dp[][]=true;
for(int i=;i<=lena;i++)
for(int j=;j<=lenb;j++)
{
if(i)
dp[i][j]|=(dp[i-][j]&&a[i]==c[i+j]);
if(j)
dp[i][j]|=(dp[i][j-]&&b[j]==c[i+j]);
}
if(dp[lena][lenb])
printf("Yes\n");
else
printf("No\n");
}
return ;
}
dpdpdpd
一开始觉得像搜索，所以也是先写了广搜，转移过程一样。
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=;
struct Node{
int i,j,k;
Node(){}
Node(int i,int j,int k):i(i),j(j),k(k){}
}p;
char a[N],b[N],c[N];
int flag,lena,lenb,lenc;
bool vis[N][N];
void bfs()
{
for(int i=;i<=lena;i++)
for(int j=;j<=lenb;j++)
vis[i][j]=;
flag=;
queue<Node> q;
q.push(Node(,,));
while(!q.empty())
{
p=q.front();
q.pop();
if(p.i==lena&&p.j==lenb&&p.k==lenc)
{
flag=;
return ;
}
if(p.i+<=lena&&p.k+<=lenc&&a[p.i+]==c[p.k+]&&!vis[p.i+][p.j])
{
vis[p.i+][p.j]=;
q.push(Node(p.i+,p.j,p.k+));
}
if(p.j+<=lenb&&p.k+<=lenc&&b[p.j+]==c[p.k+]&&!vis[p.i][p.j+])
{
vis[p.i][p.j+]=;
q.push(Node(p.i,p.j+,p.k+));
}
}
}
int main()
{
while(~scanf("%s",a+))
{
scanf("%s",b+);
scanf("%s",c+);
lena=strlen(a+);
lenb=strlen(b+);
lenc=strlen(c+);
if(lena+lenb!=lenc)
{
printf("No\n");
continue;
}
bfs();
if(flag)
printf("Yes\n");
else
printf("No\n");
}
return ;
}
搜索搜索搜索