$确定滑行方向后就转化为了LIS问题,原问题相当于正向和反向以a_i为结尾的最长上升子序列长度,$
$分别正向和反向各进行一次LIS,取得最大值即可。$
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N],f[N];
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
memset(a,0,sizeof(a));
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i]){
f[i]=max(f[i],f[j]+1); //注意是f[i]
}
}
res=max(res,f[i]);
}
for(int i=n;i>=1;i--){
f[i]=1;
for(int j=n;j>i;j--){
if(a[j]<a[i]){
f[i]=max(f[i],f[j]+1);
}
}
res=max(res,f[i]);
}
cout<<res<<endl;
}
}
$也可以转化为正向的最长上升子序列和正向的最长下降子序列$
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N];
int a[N];
int T,n;
int main(){
cin>>T;
while(T--){
memset(f,0,sizeof(f));
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(a[j]<a[i]){
f[i]=max(f[i],f[j]+1);
}
}
res=max(res,f[i]);
}
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(a[j]>a[i]){
f[i]=max(f[i],f[j]+1);
}
}
res=max(res,f[i]);
}
cout<<res<<endl;
}
}
转化为正向的最长上升子序列和正向的最长下降子序列 这样真的行吗? 正向最长上升并不等价于反向最长下降吧, 正向最长不降应该三等价于反向最长下降。 有个等于号的问题