• 注册
当前位置：1313e > 默认分类 >正文

最长****子序列

（在研读大佬写的博客后，打算记录下自己学习过程）

 

通过最长上升子序列的拓展了解到，其实这是一个系列的问题主要代表有：

1 最长上升子序列

2 最长不上升子序列

3 最长下降子序列

4 最长不下降子序列

就以最长上升子序列为例。（注意：这里面说的子序列不连续的）

得到一个数组，求这个数组的最长上升子序列长度

3 1 2 1 8 5 6

可以直接看出来这个数组的最长上升子序列是1 2 5 6，其长度也就是4.一眼就能看出来，但是用代码该怎么实现呢？

介绍俩种方法：

dp思想 

只能用于数据小的情况，要不然会TLE

目前为止所接触的dp思想核心就在状态转移方程上。同时也用到了贪心的思想。在所有的上升序列中最开始的长度都是1（算上它自身）。那么这个时候就只要考虑以arr[i]结尾的子序列中使其最长即可。找到arr[i]然后在从头开始枚举，只要满足arr[j]

brr[1]=1  （本身长度为1）

brr[2]=1;

brr[3]=2;

brr[4]=1;

brr[5]=3;

.......以此类推

#include
#include
#include
#include
#include
#include
#include
//#include
#include
#include
//#include 
#include
#include
#include
#define dbug cout<<"hear!"<=c;a--)
#define no cout<<"NO"<,greater >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair PII;
typedef pair PDD;
const int N = 4e5 + 5;
const int  INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// ll gcdd(ll a, ll b)
// {
//       while(b^=a^=b^=a%=b);    
//       return a;
// }
// void add(ll a,ll w)
// {
//   noda[++idx].b=w;
//   noda[idx].ne=h[a];
//   h[a]=idx;
// }ll h[N],idx;
const ll mod =1000000007;
ll  t, n,a,b,c,d, m, x,y, k, cnt, ans, ant, sum,q,p,num;
ll arr[N],brr[N], crr[N];
bool book[N];int main()
{IOS;cin>>n;for(ll i=1;i<=n;i++){cin>>arr[i];}for(ll i=1;i<=n;i++)//最长上升子序列{brr[i]=1;for(ll j=1;jarr[j]){brr[i]=max(brr[i],brr[j]+1);}}}for(ll i=1;i<=n;i++)//最长下降子序列{brr[i]=1;for(ll j=1;j=arr[j]){brr[i]=max(brr[i],brr[j]+1);}}}
}

 二分思想

用于处理大型数据

先来看例子

3 1 2 1 8 5 6

 1、如图所示，可以发现找到长度为1的上升子序列，若后面的数能接到3的后面，那么一定能接到1的后面，因为1比3更好，扩展度高

2、使用q[]存储所有不同长度的上升子序列结尾的最小值

3、进来一个数arr[i]时，通过二分在q[]中找到最大的小于arri的数，就能够将arri接到该数的后面，即更新q[r + 1] = arr[i]

#include
#include
#include
#include
#include
#include
#include
//#include
#include
#include
//#include 
#include
#include
#include
#define dbug cout<<"hear!"<=c;a--)
#define no cout<<"NO"<,greater >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair PII;
typedef pair PDD;
const int N = 4e5 + 5;
const int  INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// ll gcdd(ll a, ll b)
// {
//       while(b^=a^=b^=a%=b);    
//       return a;
// }
// void add(ll a,ll w)
// {
//   noda[++idx].b=w;
//   noda[idx].ne=h[a];
//   h[a]=idx;
// }ll h[N],idx;
const ll mod =1000000007;
ll  t, n,a,b,c,d, m, x,y, k, cnt, ans, ant, sum,q,p,num;
ll arr[N],brr[N], crr[N];
bool book[N];int main()
{IOS;cin>>n;for(ll i=0;i>arr[i];}/最长上升子序列ans=0;brr[0]=-2e9;for(ll i=0;i>1;if(brr[mid]>1;if(brr[mid]>arr[i]){l=mid;}else{r=mid-1;}}brr[r+1]=arr[i];ans=max(ans,r+1);}cout<>1;if(brr[mid]<=arr[i]){l=mid;}else{r=mid-1;}}brr[r+1]=arr[i];ans=max(ans,r+1);}cout<>1;if(brr[mid]>=arr[i]){l=mid;}else{r=mid-1;}}brr[r+1]=arr[i];ans=max(ans,r+1);}cout<

   浅浅举个例子 

拦截导弹

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。

Input

输入有两行，
第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），
第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。

Output

输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。

Sample

InputcopyOutputcopy
8
300 207 155 300 299 170 158 65

6

注意细节：后一发的导弹高度不能高于前一段也就是严格小于，所以就是求最大下降子序列

#include
#include
#include
#include
#include
#include
#include
//#include
#include
#include
//#include 
#include
#include
#include
#define dbug cout<<"hear!"<=c;a--)
#define no cout<<"NO"<,greater >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair PII;
typedef pair PDD;
const int N = 4e5 + 5;
const int  INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// ll gcdd(ll a, ll b)
// {
//       while(b^=a^=b^=a%=b);    
//       return a;
// }
// void add(ll a,ll w)
// {
//   noda[++idx].b=w;
//   noda[idx].ne=h[a];
//   h[a]=idx;
// }ll h[N],idx;
const ll mod =1000000007;
ll  t, n,a,b,c,d, m, x,y, k, cnt, ans, ant, sum,q,p,num;
ll arr[N],brr[N], crr[N];
bool book[N];int main()
{IOS;cin>>n;for(ll i=0;i>arr[i];}rep(i,1,n){brr[i]=1;rep(j,1,i){if(arr[i]

本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 162202241@qq.com 举报，一经查实，本站将立刻删除。

最新评论

欢迎您发表评论:

请登录之后再进行评论

登录
相关推荐
Copyright © 2023 - 2024 1313e All Rights Reserved