HDU 1257 最少拦截系统 最长递增子序列 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
",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
", ans);
	}

	return 0;
}