题目大意：给你三个串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位置，然后判断是否匹配即可。
1 #include2 #include 3 const int N=2118; 4 bool dp[N][N]; 5 char a[N],b[N],c[N]; 6 int main() 7 { 8 while(~scanf("%s",a+1)) 9 {10 scanf("%s",b+1);11 scanf("%s",c+1);12 int lena=strlen(a+1),lenb=strlen(b+1),lenc=strlen(c+1);13 if(lena+lenb!=lenc)//c的长度肯定得是等于a和b之和 14 {15 printf("No\n");16 continue;17 }18 for(int i=0;i<=lena;i++)19 for(int j=0;j<=lenb;j++)20 dp[i][j]=false;21 dp[0][0]=true;22 for(int i=0;i<=lena;i++)23 for(int j=0;j<=lenb;j++)24 {25 if(i)26 dp[i][j]|=(dp[i-1][j]&&a[i]==c[i+j]);27 if(j)28 dp[i][j]|=(dp[i][j-1]&&b[j]==c[i+j]);29 }30 if(dp[lena][lenb])31 printf("Yes\n");32 else33 printf("No\n");34 }35 return 0;36 }
一开始觉得像搜索，所以也是先写了广搜，转移过程一样。
1 #include2 #include 3 #include 4 using namespace std; 5 const int N=2118; 6 struct Node{ 7 int i,j,k; 8 Node(){} 9 Node(int i,int j,int k):i(i),j(j),k(k){}10 }p;11 char a[N],b[N],c[N];12 int flag,lena,lenb,lenc;13 bool vis[N][N];14 void bfs()15 {16 for(int i=0;i<=lena;i++)17 for(int j=0;j<=lenb;j++)18 vis[i][j]=0;19 flag=0;20 queue q;21 q.push(Node(0,0,0));22 while(!q.empty())23 {24 p=q.front();25 q.pop();26 if(p.i==lena&&p.j==lenb&&p.k==lenc)27 {28 flag=1;29 return ;30 }31 if(p.i+1<=lena&&p.k+1<=lenc&&a[p.i+1]==c[p.k+1]&&!vis[p.i+1][p.j])32 {33 vis[p.i+1][p.j]=1;34 q.push(Node(p.i+1,p.j,p.k+1));35 }36 if(p.j+1<=lenb&&p.k+1<=lenc&&b[p.j+1]==c[p.k+1]&&!vis[p.i][p.j+1])37 {38 vis[p.i][p.j+1]=1;39 q.push(Node(p.i,p.j+1,p.k+1));40 }41 }42 }43 int main()44 {45 while(~scanf("%s",a+1))46 {47 scanf("%s",b+1);48 scanf("%s",c+1);49 lena=strlen(a+1);50 lenb=strlen(b+1);51 lenc=strlen(c+1);52 if(lena+lenb!=lenc)53 {54 printf("No\n");55 continue;56 }57 bfs();58 if(flag)59 printf("Yes\n");60 else61 printf("No\n");62 }63 return 0;64 }