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:这个题怎么优化啊~我4500ms过掉的,请大牛指教In Reply To:这个题怎么优化啊~我4500ms过掉的,请大牛指教 Posted by:justjude at 2007-07-24 16:18:30 > 我照着lrj书上的算法做的,但是不知道怎么优化啊 > #include <iostream> > #define sqr(a) ( (a) * (a) ) > int s[201][201][201] , cl[201] , len[201] , po[201][201][201][101]; > > int f(int i , int j , int k) > { > if(s[i][j][k] > -1) return s[i][j][k]; > int p , tmp; > tmp = f(i , j-1 , 0 ) + sqr(k+len[j]) ; > for (p = i ; p < j ; p++ ) > { > if(cl[p]==cl[j])tmp = std::max( tmp , f(i , p , k+len[j])+f(p+1 , j-1, 0) ); > } > s[i][j][k] = tmp; > return tmp; > } > > int main() > { > int t , n , i , j , k , m , a ; > scanf("%d" , &t); > for (int ca=1; ca <= t ; ca++ ) > { > scanf("%d" , &n); > i = 1; > scanf("%d" , &a); > cl[i] = a; > len[i] = 1; > n--; > while(n--) > { > scanf("%d" , &a); > if (a == cl[i]) > { > len[i]++; > } > else > { > cl[++i] = a; > len[i] = 1; > } > } > m = i; > for(i = 0 ; i <= m ; i++) > for ( j = 0; j <= m ; j++ ) > for ( k = 0; k <= m ; k++ ) > s[i][j][k] = -1; > for( i = 1 ; i <= m ; i++) s[i][i-1][0] = 0; > a = f( 1 , m , 0); > printf("Case %d: %d\n" , ca , a); > } > return 0; > } 此程序还稍有问题, 1 21 1 1 1 2 1 1 1 3 1 1 1 1 1 3 3 3 3 3 3 3 3这组样例跑不出187=1+1+121+64 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator