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

Re:请问这题能否这样子递推的做;还有是为什么这样子会超时,不也是n2的算法吗?thx~

Posted by clearriver at 2006-10-15 17:18:16 on Problem 1159
In Reply To:请问这题能否这样子递推的做;还有是为什么这样子会超时,不也是n2的算法吗?thx~ Posted by:chgsh8089 at 2006-09-02 00:35:52
> tle的代码:
>    #include  < iostream > 
> #include  < stdio.h > 
>  using   namespace  std;
>  short  a[ 5010 ][ 5010 ]  =    { 0 } ;
>  char  p[ 5010 ];
>  int  main()
>   {
>      int  l;
>      int  i, j , t, k  =   1 ;
>      while (scanf( " %d%s " , & l,p) != EOF)
>       {
>         k  =   1 ;
>          // 下面for语句产生l=5000的测试数据; 
>     /**/ /*        l = 5000;
>         for(i = 0; i < 5000; i++)
>             p[i] = 'b';
>         p[0] = '1';
>         p[i] = '\0';
>          */ 
>          for (t  =   1 ; t  <  l; t ++ )
>           {
>             for (i  =   0 ;i < l - t;i ++ )
>              {
>                j  =  i  +  t;
>                 if (p[i]  ==  p[j])  {
>                      // k++;
>                     // 把下面的换成k++对 l=5000 这组数据时间就不用那么多了,为什么啊?不都是一次运算么,运算时间不是相同的?自己觉得很奇怪...
>                     a[i][j]  =  a[i + 1 ][j - 1 ];
>                } 
>                  else  {
>                      if (a[i + 1 ][j] < a[i][j - 1 ])a[i][j] = a[i + 1 ][j] + 1 ;
>                      else  a[i][j] = a[i][j - 1 ] + 1 ;
>                } 
>  
>            } ;
>         } ;
>         printf( " %d\n " , a[ 0 ][l - 1 ]);
>     } 
>      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