PKU 2192 Zipper 的解题报告

题目分析：题目大致意思是让你判断字符串三是否可以由字符串1,2组合而成，前提是字符串1,2的字母前后顺序不改变。
              又是一个动态规划题目，用dp[i][j]表示字符串a的前i个和字符串b的前j个和字符串c的前i+j-1段匹配的逻辑值。分析可知：要求得dp[i][j]，可以划分为两个子问题：1

dp[i-1][j]&&a[i-1]==c[j+i-1] or 2:dp[i][j-1]&&b[j-1]==c[i+j-1]。 如果这两个任何一个可以满足，则dp[i][j]=true;否则dp[i][j]=false.

             状态转移方程：dp[i][j]=( (dp[i-1][j]and a[i-1]==c[i+j-1]) or (dp[i][j-1] and b[j-1]==c[i+j-1]) );

  源程序：

#include<iostream>

       #include<cstring>

       using namespace std;

       int main(){

                char a[201],b[201],c[401];

                 int dp[201][201];

                 int n;

                 cin>>n;

                  for(int k=1;k<=n;k++){

                         scanf("%s%s%s",a,b,c);

                         int len1=strlen(a),len2=strlen(b);

                         for(int i=0;i<=len1;i++)

                                   for(int j=0;j<=len2;j++)

                                                if(i==0||j==0)

                                                       dp[i][j]=1;

                                                  else

                                                         if( (dp[i-1][j]&&a[i-1]==c[i+j-1]) || (dp[i][j-1] && b[j-1]==c[i+j-1]))  

                                                                     dp[i][j]=1;

                                                          else

                                                                      dp[i][j]=0;     

                         if(dp[len1][len2]==1)

                                   printf("Data set %d: yes\n",k);
                         else
                                   printf("Data set %d: no\n",k);          

                  }                 

         }

总结：在写代码的时候注意i，j是从0开始遍历到len1,len2，因为计算第一个是以前一个为真为前提的，所以i==0或者j==0时，应该赋真值。