当前位置:网站首页>Linear DP acwing 895 Longest ascending subsequence
Linear DP acwing 895 Longest ascending subsequence
2022-07-02 12:43:00 【T_ Y_ F666】
linear DP AcWing 895. Longest ascending subsequence
Original link
AcWing 895. Longest ascending subsequence
Algorithm tags
Dynamic programming linear DP Longest ascending subsequence
Ideas
Time complexity is represented by States * State calculation
State means One dimensional array N
State calculation Enumerate one-dimensional arrays N
Time complexity O ( N 2 ) O(N^2) O(N2)
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 = 1005, INF = 0x3f3f3f3f;
int a[N], f[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 n=read();
rep(i, 1, n+1){
a[i]=read();
}
rep(i, 1, n+1){
// initialization f[i] Only a[i] In itself The length is 1
f[i]=1;
rep(j, 1, i){
if(a[j]<a[i]){
f[i]=max(f[j]+1, f[i]);
}
}
}
int ans=0;
rep(i, 1, n+1){
ans=max(ans, f[i]);
}
printf("%lld", ans);
return 0;
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
- 模数转换器(ADC) ADE7913ARIZ 专为三相电能计量应用而设计
- Mui WebView down refresh pull-up load implementation
- 8A 同步降压稳压器 TPS568230RJER_规格信息
- Shutter encapsulated button
- Js10day (API phased completion, regular expression introduction, custom attributes, filtering sensitive word cases, registration module verification cases)
- C#运算符
- Deep copy event bus
- 百款拿来就能用的网页特效,不来看看吗?
- 哈希表 AcWing 841. 字符串哈希
- . Net, C # basic knowledge
猜你喜欢
Heap acwing 839 Simulated reactor
Anxiety of a 211 programmer: working for 3 years with a monthly salary of less than 30000, worried about being replaced by fresh students
Record the range of data that MySQL update will lock
There is a hidden danger in CDH: the exchange memory used by the process of this role is XX megabytes. Warning threshold: 200 bytes
线性DP AcWing 897. 最长公共子序列
Why do programmers have the idea that code can run without moving? Is it poisonous? Or what?
Sparkcontext: error initializing sparkcontext solution
Adding database driver to sqoop of cdh6
Lekao.com: experience sharing of junior economists and previous candidates in customs clearance
Drools dynamically add, modify, and delete rules
随机推荐
模块化 CommonJS ES Module
Docsify deploy IIS
区间DP AcWing 282. 石子合并
线性DP AcWing 896. 最长上升子序列 II
Find the common ancestor of any two numbers in a binary tree
Docker compose configuration mysql, redis, mongodb
一些突然迸发出的程序思想(模块化处理)
Interview questions for software testing - a collection of interview questions for large factories in 2022
Redis introduction, scenario and data type
Direct control PTZ PTZ PTZ PTZ camera debugging (c)
std::vector批量导入快速去重方法
JS6day(DOM结点的查找、增加、删除。实例化时间,时间戳,时间戳的案例,重绘和回流)
Sse/avx instruction set and API of SIMD
spfa AcWing 852. SPFA judgement negative ring
中国交通标志检测数据集
Dijkstra AcWing 850. Dijkstra求最短路 II
Lekao: 22 year first-class fire engineer "technical practice" knowledge points
接口测试面试题目,你都会了吗?
C#运算符
线性DP AcWing 895. 最长上升子序列