最长下降子序列
1.
最长下降子序列，指的便是一个序列中，数字依次减小且长度最长的序列。
例如 7 4 3 2 8 9 10 中 7 4 3 2 便是该序列的最长下降子序列
那一个序列的最长下降子序列怎么求呢？
有两种复杂度不同的做法，下面先介绍n2做法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1e5;
int a[maxn];
// read()为快输 可忽略
inline int read(){
int ret=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-f;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+(ch^'0');
ch=getchar();
}
return f*ret;
}
int n;//n为读入序列的长度
int dp[maxn]; //dp[i]表示以i为结尾的最长下降子序列长度
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){//枚举每一个结尾
dp[i]=1;//初始化，以i结尾的最长下降子序列初值为1，即为它本身
for(int j=1;j<i;j++){//枚举i之前的每一个数，来更新dp[i];
if(a[j]>a[i]&&dp[i]<dp[j]+1){//更新条件，在下面解释；
dp[i]=dp[j]+1; //那么，就对dp[i]进行更新，+1是应为将a[i]加入
}
}
}
/*
更新条件便是：之前下降子序列的末尾值要比目前a[i]大，说明a[i]可以接在后面
而且目前dp[i]的值要比将a[i]接入先前的值小，便可以更新
*/
int ans=-1;
for(int i=1;i<=n;i++){
if(dp[i]>ans)
ans=dp[i]; //找最大
}
cout<<ans;//输出
return 0;
}
2.
观察上述算法
显然可以在更新的过程中做了大量无意义操作
我们可以利用二分查找进行优化将其由n2
优化到nlogn;
该算法二分查找部分挺有意思
可以手推一下
当然认为麻烦可以直接用
upper_bound(),本质是一样的
接下来介绍nlogn做法·
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1e5;
int a[maxn];
int dp[maxn]; //dp[i]为长度为i的下降序列的最大值
//快输，可忽略
inline int read(){
int ret=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-f;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+(ch^'0');
ch=getchar();
}
return f*ret;
}
int n;
int main(){
//freopen("a.in","r",stdin);
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
dp[0]=0x3f3f3f3f;//预处理dp0，避免对dp[0]进行更改，本质上也可理解为二分边界
dp[1]=a[1];//将第一个值加入
int len=1;
for(int i=2;i<=n;i++)
{
int l=0,r=len,mid;//二分查找部分
if(a[i]<=dp[len])dp[++len]=a[i];//如果新加入的值可以直接更新，那便更新
else
/*如果不能更新，在已有的dp数组从左至右查找a[i]第一个大于等于的值的下标
我们采用二分查找的方式
*/
{
while(l<r)
{
mid=(l+r+1)/2;
if(dp[mid]<a[i])r=mid-1;
else l=mid;
}
dp[l+1]=a[i];
}
}
cout<<len;//最后的len就是最长下降子序列的长度；
return 0;
}
该算法本质上为贪心的运用
既然要求最长下降子序列
那么一个下降序列末尾的值越大，对后加入的数贡献也就越大
我们二分部分正是在更新末尾的最大值以对长度贡献。
个人觉得二分部分太麻烦
以下这个对其进行了一下简化，但本质是相同的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int maxn=1e5;
int a[maxn];
int dp[maxn];
inline int read(){
int ret=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-f;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+(ch^'0');
ch=getchar();
}
return f*ret;
}
int n;
bool cmp(int x,int y){
return x>y;
}
int main(){
// freopen("a.in","r",stdin);
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
dp[1]=a[1];
int len=1;
for(int i=2;i<=n;i++)
{
int l=0,r=len,mid;
if(a[i]<=dp[len])dp[++len]=a[i];
else
dp[upper_bound(dp+1,dp+1+len,a[i],cmp)-dp]=a[i];
}
}
cout<<len;
return 0;
}
3
在学习完之后
我们来进行一些练习
1 .洛谷p1493
贴一发ac代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<string>
using namespace std;
const int maxn=1e5;
int a[maxn];
int dp[maxn];
inline int read(){
int ret=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-f;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+(ch^'0');
ch=getchar();
}
return f*ret;
}
int n;
map<int,int >ma;
int b[maxn];
int main(){
// freopen("a.in","r",stdin);
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
ma[a[i]]=i;
}
for(int i=1;i<=n;i++){
b[i]=read();
}
dp[0]=0x3f3f3f3f;
dp[1]=ma[b[1]];
int len=1;
for(int i=2;i<=n;i++)
{
int l=0,r=len,mid;
if(ma[b[i]]>=dp[len])dp[++len]=ma[b[i]];
else
{
while(l<r)
{
mid=(l+r+1)/2;
if(dp[mid]>ma[b[i]])r=mid-1;
else l=mid;
}
dp[l+1]=ma[b[i]];
}
}
cout<<len;
return 0;
}
有没有觉得很眼熟
就是你想的那样；
2.洛谷p1020
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
const int maxn=1e5;
int a[maxn];
int dp[maxn]; //dp[i]为长度为i的下降序列的最大值
//快输，可忽略
inline int read(){
int ret=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-f;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+(ch^'0');
ch=getchar();
}
return f*ret;
}
int n;
bool cmp(int x,int y){
return x>y;
}
int main(){
// freopen("a.in","r",stdin);
while(cin>>a[++n]);
n--;
dp[1]=a[1];
int len=1;
for(int i=2;i<=n;i++)
{
int l=0,r=len,mid;
if(a[i]<=dp[len])dp[++len]=a[i];
else {
dp[upper_bound(dp+1,dp+1+len,a[i],cmp)-dp]=a[i];
}
}
cout<<len<<endl;
memset(dp,0,sizeof(dp));
dp[1]=a[1];
len=1;
for(int i=2;i<=n;i++)
{
int l=0,r=len,mid;
if(a[i]>dp[len])dp[++len]=a[i];
else
{
dp[lower_bound(dp+1,dp+1+len,a[i])-dp]=a[i];
}
}
cout<<len;
return 0;
}
这道题的本质就是将上升序列与下降序列的结合，可以说是模板题吧