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:这个题怎么优化啊~我4500ms过掉的,请大牛指教

Posted by huicpc0838 at 2010-12-05 10:00:09 on Problem 1390
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:
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