> 使用了滚动数组来减少内存．已经郁闷两天了
> #include <stdio.h>
> #define MAXN 501
> int a[MAXN], b[MAXN];
> int d[2][MAXN][MAXN], cur[2][MAXN][MAXN], path[2][MAXN][MAXN], c[2][MAXN];
> int stack[MAXN], top;
> int m, n;
> int p1=0, p2=1;
> void print_rev( int t )
> {
> 	if( path[p1][n][t] != 0) print_rev( path[p1][n][t] );
> 	printf("%d ", a[t]);	
> }
> void print()
> {
> 	
> 	int t = cur[p1][n][c[p1][n]];
> 	top = 0;
> 	while( t )
> 	{
> 		stack[top++] = a[t];
> 		t = path[p1][n][t];
> 	}
> 	while( top )
> 	{
> 		printf("%d ", stack[--top]);	
> 	}
> 	putchar('\n');
> }
> int main()
> {
> 	// freopen("2127.in", "r", stdin);
> 	int i, j;
> 	scanf("%d", &m);
> 	for(i=1; i<=m; ++i) scanf("%d", &a[i]);
> 	scanf("%d", &n);
> 	for(j=1; j<=n; ++j) scanf("%d", &b[j]);
> 	for(i=1; i<=m; ++i) 
> 	{
> 		int k;
> 		for(j=1; j<=n; ++j)
> 		{
> 			if( a[i] == b[j])			// 发现了公共元素
> 			{
> 				c[p2][j] = c[p1][j-1];
> 				for(k=1; k<=m; ++k)	
> 				{
> 					d[p2][j][k] = d[p1][j-1][k]; 
> 					cur[p2][j][k] = cur[p1][j-1][k];
> 					path[p2][j][k] = path[p1][j-1][k];
> 				}
> 					
> 				int lo, hi, mid;
> 				lo = 1; hi = c[p2][j];
> 				while( lo <= hi)
> 				{
> 					mid = ( lo + hi ) >> 1;
> 					if( a[i] > d[p2][j][mid] ) lo = mid + 1;
> 					else hi = mid - 1;
> 				}
> 				d[p2][j][lo] = a[i];
> 				cur[p2][j][lo] = i;
> 				if( lo > 1 ) path[p2][j][i] = cur[p2][j][lo-1];
> 				else path[p2][j][i] = 0;
> 				if( lo > c[p2][j] ) c[p2][j]++;
> 			}
> 			else 
> 			{
> 				if( c[p2][j-1] >= c[p1][j] )
> 				{
> 					c[p2][j] = c[p2][j-1];
> 					for(k=1; k<=m; ++k)
> 					{
> 						d[p2][j][k] = d[p2][j-1][k];
> 						cur[p2][j][k] = cur[p2][j-1][k];
> 						path[p2][j][k] = path[p2][j-1][k];
> 					}
> 				}
> 				else
> 				{
> 					c[p2][j] = c[p1][j];
> 					for(k=1; k<=m; ++k)
> 					{
> 						d[p2][j][k] = d[p1][j][k];
> 						cur[p2][j][k] = cur[p1][j][k];
> 						path[p2][j][k] = path[p1][j][k];
> 					}
> 				} // end else
> 			}// end else
> 		}
> 		int t = p1; p1 = p2; p2 = t;			// 数组滚动
> 	}
> 	printf("%d\n", c[p1][n]);
> 	print();
> 	//print_rev( cur[p1][n][c[p1][n]]) ;
> 	// putchar('\n');
> 	return 0;
> }

• Re:这个dp过程对不对？我加了discus说的优化，结果TlE->WA (14) navyakula 2006-02-15 20:36:43
  • 我怎么感觉自己的算法是O(n^2)的啊，但wa (1508) kevin655 2006-07-13 12:09:34