| ||||||||||
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