学步园

题目链接：http://acm.hdu.edu.cn/diy/contest_showproblem.php?pid=1002&cid=18800&hide=0

腾讯2012.3.22的第三题就是基于求最长递增子序列的思想，不过是题目稍微变形了一下，求正串和反串中最大的公共递增子序列
首先给出求递增子序列的模板

#include<stdio.h>
#define M 100000

int a[M];
int dp[M];

int LIS(int nLen)
{
	//a是数据数组
	//dp是递推数组
	//nLen是数组a的长度
	int i,j;
	int nMax = 0;
	
	for(i = 0; i < nLen; ++i)
	{
		dp[i] = 1;
		for(j = 0; j < i; ++j)
		{
			if(a[i] > a[j])//如果是严格递增子序列则为>,非严格递增可取>=
			{
				dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
			}
		}
		nMax = nMax > dp[i] ? nMax : dp[i];
	}
	return nMax;
}

void main()
{
	int n;
	int i;
	int nMax;
	while(scanf("%d",&n) != EOF)
	{
		for(i = 0; i < n; ++i)
		{
			scanf("%d",&a[i]);
		}

		nMax = LIS(n);
		printf("%d\n",nMax);
	}
}

比赛的时候想到了这个层面，但是当时觉得这个复杂度是o(n^2)，所以想着怎么去优化，结果时间也过了，悲剧的没有提交，不说了，说多了全是泪啊。下面给出腾讯那道比赛题的参考代码，当然还是没有想出优化的算法。

#include<stdio.h>
#include<string.h>
#define M 210

int a[M];
int dp[M];

int LIS(int nLen)
{
	//a是数据数组
	//dp是递推数组
	//nLen是数组a的长度
	int i,j;
	int mx;
	int ans = 0;

	for(i = nLen - 1; i >= 0; --i)
	{
		mx = 0;
		for(j = 0; j <= i; ++j)
		{
			if(a[j] < a[i])//dp[j]表示j之前的递增数对的数量
			{
				mx = mx > dp[j] ? mx : dp[j];
			}
			else if(a[j] == a[i])
			{
				dp[j] = mx + 1;//这里的加1，指的是数对的数量加1
			}

			if(j < i)
			{
				ans = ans > dp[j] + dp[j] ? ans : dp[j] + dp[j];
			}
			else//如果j==i,在dp[j]=mx+1中就多加了1
			{
				ans = ans > dp[j] + dp[j] - 1 ? ans : dp[j] + dp[j] - 1;
			}
		}
	}
	return ans;
}

void main()
{
	int n;
	int t;
	int i;
	int nMax;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		memset(dp,0,sizeof(dp));
		for(i = 0; i < n; ++i)
		{
			scanf("%d",&a[i]);
		}

		nMax = LIS(n);
		printf("%d\n",nMax);
	}
}