最长子序列

最长子序列问题（two ways）

【题目描述】：

Bob 吃完烤串之后又充满了精力，现在 Alice 给了他一个难题：
有一个长度为 n 的序列a[i],
但是 Alice 修改了其中某 k个位置的值，得到新序列 b[i].
Bob 拿到序列 b 之后，希望可以改不超过 kk 个位置的值
使得 b 序列也满足有序
这个问题对他来说太难了，他想寻求你的帮助你需要告诉他如何修改使得满足要求。

【输入格式】：

第一行两个整数 n, k，意义如上所述。
接下来一行 n 个整数，第 i个整数表示b[i].

【输出格式】：

第一行一个整数 t，表示你要修改的次数。需要满足t<=k;
接下来 t行，第 i 行两个整数 
如果有多组解符合要求，输出任意一组即可。你不必最小化 t，只要满足条件即可。

【输入输出样例】：

输入样例#1： 复制
5 1
1 2 7 4 5
输出样例#1： 复制
1
3 3
输入样例#2： 复制
5 2
1 2 3 4 5
输出样例#2： 复制
0
输入样例#3： 复制
5 5
5 4 3 2 1
输出样例#3： 复制
4
1 1
2 1
3 1
4 1
输入样例#4： 复制
5 0
1 2 3 4 5
输出样例#4： 复制
0

分析：
实质上是一个最长子序列问题，如果找到最长子序列长度LIS，那么需要进行更改次数为 n-LIS，每次跑循环找到不在LIS中的数据改为前一个或后一个LIS中的数据即可。

【参考代码】：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5005 ;

int a[MAXN],SK[MAXN];
int main()
{
int  n, k;
cin>>n>>k; 
for( int i = 1; i <= n ; ++i)
	cin>>a[i]; 
int len = 1;
SK[len] = a[1] ;
for( int i = 2 ; i <= n ; ++i){
	if( a[i] > SK[len])
		SK[++len] = a[i];
	else {
		int j = lower_bound(SK+1,SK+len+1,a[i])-SK;
		SK[j] = a[i] ;
	}	
}
int cnt = 1;
cout<< n-len <<endl;
for( int i = 1; i <= n; ++i){
	if( a[i] == SK[cnt] ) cnt++;
	else {
		cout<< i <<" "<< SK[cnt-1] <<endl;
	} 
}
return 0;

}

1. 复杂度为O（n^2）
   朴素算法， 代码如下：

    	#include<cstdio>//或者用bits万能库
    	using namespace  std;
    	const int MAX=1001;
    	int a[MAX];
    	int lis(int x)
    {
   	 int num[MAX];
   	 for(int i=0;i<x;i++)
    	{
        num[i]=1;
        for(int j=0;j<i;j++)
        {
            if(a[j]<a[i]&&num[j]+1>num[i])//每次都在之前找是否能替换当前最大子序列长度
                   num[i]=num[j]+1;
        }
    }
    int maxx=0;
    for(int i=0;i<x;i++)
        if(maxx<num[i])
            maxx=num[i];
    return maxx;}
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	for(int i=0;i<n;i++)
        	scanf("%d",&a[i]);
    	printf("%d\n",lis(n));
    	return 0;
    }
   

2.复杂度为O (nlogn)
复杂度降低主要是利用了二分的思想，代码如下：

	#include<cstdio>
	#include<algorithm>//或者用bits万能库
	using namespace std;
	const int MAXN=200001;
	int a[MAXN];
	int d[MAXN];
	int main()
	{
	 int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
    	scanf("%d",&a[i]);
	d[1]=a[1];
	int len=1;
	for(int i=2;i<=n;i++)
	{
    	if(a[i]>d[len])
          d[++len]=a[i];
    else
    {
        int j=std::lower_bound(d+1,d+len+1,a[i])-d;
//lower_bound()作用：找到在某有序序列中大于等于x的第一个数的位置，返回值；
        d[j]=a[i];
    }
}
	printf("%d\n",len);    
	return 0;}

希望这些能够对大家有帮助，谢谢大家…………