当前位置:网站首页>The longest ascending subsequence model acwing 1017 Strange thief Kidd's glider
The longest ascending subsequence model acwing 1017 Strange thief Kidd's glider
2022-07-07 08:51:00 【T_ Y_ F666】
Longest ascending subsequence model AcWing 1017. Kidd's glider
Original link
Algorithm tags
DP linear DP Longest ascending subsequence
Ideas
Code
#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] End point Pass from left to right a[j] The longest distance
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] End point Pass from right to left a[j] The longest distance
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);
}
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
- idea里使用module项目的一个bug
- oracle一次性说清楚,多种分隔符的一个字段拆分多行,再多行多列多种分隔符拆多行,最终处理超亿亿。。亿级别数据量
- [Yu Yue education] basic reference materials of electrical and electronic technology of Nanjing Institute of information technology
- redis故障处理 “Can‘t save in background: fork: Cannot allocate memory“
- Basic data types and string types are converted to each other
- opencv之图像分割
- [kuangbin] topic 15 digit DP
- [Yugong series] February 2022 U3D full stack class 007 - production and setting skybox resources
- 平台化,强链补链的一个支点
- 数字三角形模型 AcWing 275. 传纸条
猜你喜欢
opencv之图像分割
LeetCode 736. LISP syntax parsing
Greenplum6.x搭建_安装
Compilation and linking of programs
let const
Rapid integration of authentication services - harmonyos platform
MySQL主从延迟的解决方案
Componentspace2022, assertions, protocols, bindings, and configuration files
[MySQL] detailed explanation of trigger content of database advanced
路由信息协议——RIP
随机推荐
[Chongqing Guangdong education] organic electronics (Bilingual) reference materials of Nanjing University of Posts and Telecommunications
Greenplum 6.x build_ Environment configuration
Data type - integer (C language)
Mock. JS usage details
How to realize sliding operation component in fast application
Componentspace2022, assertions, protocols, bindings, and configuration files
FPGA knowledge accumulation [6]
Explain Huawei's application market in detail, and gradually reduce 32-bit package applications and strategies in 2022
Gson转换实体类为json时报declares multiple JSON fields named
Introduction to data fragmentation
9c09730c0eea36d495c3ff6efe3708d8
Find the original code, inverse code and complement of signed numbers [C language]
Quick sorting (detailed illustration of single way, double way, three way)
[kuangbin] topic 15 digit DP
Tronapi wave field interface - source code without encryption - can be opened twice - interface document attached - package based on thinkphp5 - detailed guidance of the author - July 6, 2022 - Novice
About using CDN based on Kangle and EP panel
[Yu Yue education] higher vocational English reference materials of Nanjing Polytechnic University
ncs成都新電面試經驗
Gson converts the entity class to JSON times declare multiple JSON fields named
leetcode135. Distribute candy