AcWing 3549. 最长非递减子序列
原题链接
困难
作者:
梨小畅
,
2021-05-23 13:34:41
,
所有人可见
,
阅读 324
找最长“好”子序列 。具体请去看抽风大佬的题解
法1
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int pre[N][2]; // pre[i][j]:[1,i] 区间内最长不下降子序列的长度,且最长不下降子序列最后一个字符为j(j为0或1)
int nex[N][2]; // next[i][j]: [i,n] 区间内最长不下降子序列的长度,且最长不下降子序列第一个字符为j(j为0或1)
int a[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],a[i]--; // 把1、2 变成 0、1
// 求 pre
for(int i=1;i<=n;i++){
if(a[i]==0) {
pre[i][0]=pre[i-1][0]+1;
pre[i][1]=pre[i-1][1];
}
else{
pre[i][1]=max(pre[i-1][0],pre[i-1][1])+1;
pre[i][0]=pre[i-1][0];
}
}
// 求 nex
for(int i=n;i;i--){
if(a[i]==0){
nex[i][0]=max(nex[i+1][0],nex[i+1][1])+1;
nex[i][1]=nex[i+1][1];
}
else{
nex[i][1]=nex[i+1][1]+1;
nex[i][0]=nex[i+1][0];
}
}
// 求maxm
int maxm=-1;
for(int i=1;i<=n;i++) {
maxm=max(maxm,max(pre[i][0]+nex[i+1][0],pre[i][0]+nex[i+1][1]));
maxm=max(maxm,max(pre[i][1]+nex[i+1][0],pre[i][1]+nex[i+1][1]));
}
cout<<maxm<<endl;
return 0;
}
算法2
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int f[N][5]; // f[i][j]:区间[1,i]内 最长好子序列的长度,且该最长好子序列的最后一个字符在第j部分 (j可取值1、2、3、4)
int a[N];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],a[i]--; // 把1、2 变成 0、1
for(int i=1;i<=n;i++){
if(a[i]==1){
f[i][2]=max(f[i-1][1],f[i-1][2])+1;
f[i][4]=max(f[i-1][4],f[i-1][3])+1;
f[i][1]=f[i-1][1];
f[i][3]=f[i-1][3];
}
else{
f[i][1]=f[i-1][1]+1;
f[i][3]=max(f[i-1][3],f[i-1][2])+1;
f[i][2]=f[i-1][2];
f[i][4]=f[i-1][4];
}
}
int res=-1;
for(int i=1;i<=4;i++) res=max(res,f[n][i]);
cout<<res<<endl;
return 0;
}