当前位置:网站首页>最长上升子序列模型 AcWing 1017. 怪盗基德的滑翔翼
最长上升子序列模型 AcWing 1017. 怪盗基德的滑翔翼
2022-07-07 06:11:00 【T_Y_F666】
最长上升子序列模型 AcWing 1017. 怪盗基德的滑翔翼
原题链接
算法标签
DP 线性DP 最长上升子序列
思路
代码
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 105, INF = 0x3f3f3f3f;
int f[N], a[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=read();
while(t--){
int n=read();
rep(i, 1, n+1){
a[i]=read();
}
int ans=0;
// a[i]为终点 从左到右经过a[j]的最长距离
rep(i, 1, n+1){
f[i]=1;
rep(j, 1, i){
if(a[j]<a[i]){
f[i]=max(f[i], f[j]+1);
}
}
ans=max(ans, f[i]);
}
// a[i]为终点 从右到左经过a[j]的最长距离
Rep(i, n, 0){
f[i]=1;
Rep(j, n, i+1){
if(a[j]<a[i]){
f[i]=max(f[i], f[j]+1);
}
}
ans=max(ans, f[i]);
}
printf("%lld\n", ans);
}
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
猜你喜欢
leetcode134. gas station
2-3查找樹
Opencv learning note 4 - expansion / corrosion / open operation / close operation
Image segmentation in opencv
How to realize the high temperature alarm of the machine room in the moving ring monitoring system
Novice entry SCM must understand those things
【踩坑】nacos注册一直连接localhost:8848,no available server
2 - 3 arbre de recherche
PLSQL的安装和配置
Rapid integration of authentication services - harmonyos platform
随机推荐
Count sort (diagram)
The field value in Splunk subquery fuzzy matching CSV is*
Analysis of using jsonp cross domain vulnerability and XSS vulnerability in honeypot
Database storage - table partition
Sign and authenticate API interface or H5 interface
[Yugong series] February 2022 U3D full stack class 008 - build a galaxy scene
Three series of BOM elements
Opencv learning notes 1 -- several methods of reading images
Rapid integration of authentication services - harmonyos platform
How to integrate app linking services in harmonyos applications
2-3查找樹
2-3 lookup tree
Through the "last mile" of legal services for the masses, fangzheng Puhua labor and personnel law self-service consulting service platform has been frequently "praised"
Several ways of lambda used in functions in kotlin (higher-order functions)
String operation
详解华为应用市场2022年逐步减少32位包体上架应用和策略
[Nanjing University] - [software analysis] course learning notes (I) -introduction
[Chongqing Guangdong education] audio visual language reference materials of Xinyang Normal University
下载和安装orcale database11.2.0.4
Download and install orcale database11.2.0.4