使用了滚动数组来减少内存．已经郁闷两天了
#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;
}

• 这个dp过程对不对？我加了discus说的优化，结果TlE->WA (2223) navyakula 2006-02-15 16:07:11
  • 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