胡一刀的博客

动态规划一题- -

                                      

题目原为英文，先简要用中文说明其大概原意。
输入s1,s2,s3。s1按顺序插在s2的空挡内，看能否组合成s3。
如：s1=cat s2=tree s3=catrtee
s1的ca插在tree的左边形成catree再把s1的t插在catree的r和e之间就形成s3
注意：s1必须按顺序插，比如s1的第一个字符c插在s2的第一二字符之间，则s1的a，t字符必须插在此时形成的新串tcree的c字符之后。
好了，题目就说道这不知道大家看懂了题意没。
输入输出格式：
输入：首先输入你要测试的情况数N(这个数的范围忘了，反正不为超过65535)，然后输入s1,s2,s3(s3的长度<1000)(空格区分)，一行为一次测试例子，总共输入N行测试例子s1,s2,s3;
输出：第i（0<i<=N）个测试例子成功组合输出Data set i: yes否则输出Data set i: no
input sample
3
cat tree catrtee
cat tree catrete
cat tree carttee

ouput sample
Data set 1: yes
Data set 2: yes
Data set 3: no

附上我的程序清单，

#include <iostream>
#include <string>
using namespace std;
void main()
{
 short int N,i,j,k,l,IsSuccess;
    string s1,s2,s3;
 cin>>N;
 for(i=0;i<N;i++)
 {
  cin>>s1>>s2>>s3;
  short int *flag1 = new short int[s1.size()];
  short int *flag3 = new short int[s3.size()];
  for(k=0;k<s1.size();k++)
   {
    flag1[k] = k;//flag1标志初始化
   }//for标志初始化
        while((flag1[0]+s1.size())<(s3.size()))
  {
   if((s1.size()+s2.size())!=s3.size()){IsSuccess = 0;break;}//长度不等，无需往下比
   //cout<<s1[0];break;
   IsSuccess = 1;
   for(k=0;k<s3.size();k++)
   {
    flag3[k] = 0;//flag3标志初始化
   }//for标志初始化
            for(j=0;j<s1.size();j++)
   {
    for(k=flag1[j];k<s3.size();k++)
    {
     if(s1[j]==s3[k])
     {
      for(l=j;l<s1.size();l++){flag1[l]=(k+l-j)>flag1[l]?k+l-j:flag1[l];}
      flag3[k]=1;
      break;
     }
    }
    if(k==s3.size()) {IsSuccess=0;break;}
   } 
   if(IsSuccess==0){break;}//失败，退出循环
   else//判断余下的是否是和s2一致，若是成功退出，否则继续循环。
   {
    short int tt = 0;
    for(k=0;k<s2.size();k++)
    { 
     for(j=tt;j<s3.size();j++)
     {
      //cout<<s2[k]<<" "<<s3[j]<<endl;
      if((flag3[j]==0)&&(s2[k]==s3[j])) {tt = j+1;break;}
      if((flag3[j]==0)&&(s2[k]!=s3[j])){IsSuccess=0;break;}
     }
     if(IsSuccess==0){break;}
    }
   }
            if(IsSuccess==1) break;
   else//所有flag1[]右移
   {
    if((flag1[0]+s1.size())==s3.size()) {IsSuccess=0;break;}//移不动了
    short int yes = 0;
    for(k=s1.size()-1;k>-1;k--)
    {
     short int ttt;
     if(k==(s1.size()-1)) ttt = s3.size();
     else ttt = flag1[k+1];
     for(j=flag1[k]+1;j<ttt;j++)
     {
      if(s1[k]==s3[j]) {yes = 1;flag1[k] = j;break;}
     }
     if(yes==1) break;
    }
    if(yes==0) {IsSuccess=0;break;}
   }
  }//while每次完成一次判断
  if(IsSuccess==1) cout<<"Data Set "<<i+1<<": yes"<<endl;
  else cout<<"Data Set "<<i+1<<": no"<<endl;
  delete flag1;delete flag3;//释放
 }//forN个循环

}

- 作者： hlq83 2005年06月11日, 星期六 16:35 加入博采