146.包含某一项最长上升子序列

2188 最长上升子序列

 

 时间限制: 1 s

 空间限制: 32000 KB

 题目等级 : 钻石 Diamond

题解

• 
  

题目描述 Description

LIS问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子序列，你还能解决吗？

    给出一个长度为N整数序列，请求出它的包含第K个元素的最长上升子序列。

    例如：对于长度为6的序列<2,7,3,4,8,5>，它的最长上升子序列为<2,3,4,5>，但如果限制一定要包含第2个元素，那么满足此要求的最长上升子序列就只能是<2,7,8>了。

输入描述 Input Description

第一行为两个整数N,K，如上所述。

    接下来是N个整数，描述一个序列。

 

输出描述 Output Description

请输出两个整数，即包含第K个元素的最长上升子序列长度。

样例输入 Sample Input

8 6

65 158 170 299 300 155 207 389

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

80%的数据，满足0

    100%的数据，满足0

分类标签 Tags 点此展开 

动态规划

基本思路：

k之前的数正常更新

设置一个flag数组判断k+1之后的数，是不是由k更新过来的。

代码：

#include< iostream >

using namespace std;

#include< cstdio >

#define N 200001

int num[N],len[N];

bool flag[N];

int n,anslen=-N;

int main()

{

int k;

scanf("%d%d",&n,&k);

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

{

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

len[i]=1;

if(i<=k&&i>=2)

{

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

{

if(len[j]+1>len[i]&&num[j]

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

}

}

flag[k]=1;

if(i>=k)

{

for(int j=k;j<=i-1;++j)

{

if(len[j]+1>len[i]&&num[j]

{

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

flag[i]=1;

}

}

if(len[i]>anslen&&flag[i])

anslen=len[i];

}

}

cout<<anslen<<endl;

return 0;

}