Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这回又WA掉了...话说gamy那个TLE...所以用下面的方法剪枝,但还是wa

Posted by cmonkey at 2009-07-12 23:59:00 on Problem 2192 and last updated at 2009-07-17 19:08:10
#include <iostream>

using namespace std;
char s[403],s1[201],s2[201];
bool f[201][201];

int main()
{   int n = 1,T;
    cin>>T;
    while(n <= T)
    {    cin>>s1>>s2>>s;
         int a[125],i = 0;
         memset(a,0,sizeof(a));
         while(i <= strlen(s1))a[s1[i++]]++;
         i = 0;
         while(i <= strlen(s2))a[s2[i++]]++;
         i = 0;
         while(i <= strlen(s))
         {       a[s[i]]--;
        
                 if (a[s[i]] < 0)
                 {  cout<<"Data set "<<n<<": no\n";
                
                    return 0;
                 }
                 i++;
         }//剪枝
         memset(f,0,sizeof(f));
         i=1;
         while(s1[i - 1]==s[i - 1]&&i<=(int)strlen(s1))f[i++][0]=1;
         i=1; 
         while(s2[i - 1]==s[i - 1]&&i<=(int)strlen(s1))f[0][i++]=1;
         for (i = 1; i <= (int)strlen(s1); i++)
         {     for (int  j = 1; j <= (int)strlen(s2); j++)
                   f[i][j] = ((f[i - 1][j] && s1[i - 1] == s[i + j -1])||
                              (f[i][j - 1] && s2[j - 1] == s[i + j - 1]));
         }      
         cout<<"Data set "<<n<<": ";
         if (f[(int)strlen(s1)][(int)strlen(s2)])
            cout<<"yes\n";
         else cout<<"no\n";
         n++;
    }

    return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator