| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:也想知道同样的问题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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator