HDU 1257 最少拦截系统 最长递增子序列

题意

这个题的意思是说给你\(n\)个数，让你找到他最长的并且递增的子序列\((LIS)\)。这里和最长公共子序列一样\((LCS)\)一样，子序列只要满足前后关系即可，不需要相邻。

解题思路

解法一：这个可以用动态规划来实现，\(dp[i]\)代表前\(i\)个数列中以第\(i\)个数为结尾的\(LIS\)的长度。递推关系如下：

复杂度为\(n^2\)。

解法二：这里一个\(dp[i]\)，但是代表是长度为\(i\)的子序列中最后一个元素是多少，这里这个元素要尽量小。因为在同等长度下，最后一个结尾的数值越小”越好“。复杂度为\(nlogn\)。效率很高了。

这个递推关系有点复杂，详情看代码实现或者搜索\(LIS\)会有相关的博客讲解。

代码实现

//解法一的形式

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=1e3+7;

int dp[maxn][2];

int n;

int main() {

	while(scanf("%d",&n)!=EOF) {

		for(int i=1; i<=n; i++) {

			scanf("%d", &dp[i][0]);

			dp[i][1]=1;

		}

		int ans=1;

		for(int i=2; i<=n; i++) {

			for(int j=1; j<i; j++) {

				if(dp[j][0] < dp[i][0] && dp[j][1]+1 > dp[i][1])

					dp[i][1]=dp[j][1]+1;

			}

			ans=max(ans, dp[i][1]);

		}

		printf("%d\n",ans);

	}

	return 0;

}

//解法二

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxn=1e3+7;

int dp[maxn], num[maxn];

int n;

int main() {

	while(scanf("%d", &n)!=EOF) {

		for(int i=1; i<=n; i++) {

			scanf("%d",&num[i]);

			dp[i]=inf;

		}

		int j, ans=0;

		for(int i=1; i<=n; i++) {

			j=lower_bound(dp+1, dp+n+1, num[i])-dp;

			ans=max(ans, j);

			dp[j]=num[i];

		}

		printf("%d\n", ans);

	}

	return 0;

}