当前位置:网站首页>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
边栏推荐
- Leetcode - Sword finger offer 59 - I, 59 - II
- 1380. Lucky numbers in the matrix [two-dimensional array, matrix]
- 中国交通标志检测数据集
- Leetcode - Sword finger offer 37, 38
- spfa AcWing 851. SPFA finding the shortest path
- Input box assembly of the shutter package
- [ybtoj advanced training guidance] cross the river [BFS]
- JS10day(api 阶段性完结,正则表达式简介,自定义属性,过滤敏感词案例,注册模块验证案例)
- VLAN experiment
- Mongodb redis differences
猜你喜欢
Deep Copy Event bus
Rust search server, rust quick service finding tutorial
Find the common ancestor of any two numbers in a binary tree
线性DP AcWing 897. 最长公共子序列
NTMFS4C05NT1G N-CH 30V 11.9A MOS管,PDF
JS7day(事件对象,事件流,事件捕获和冒泡,阻止事件流动,事件委托,学生信息表案例)
Does C language srand need to reseed? Should srand be placed in the loop? Pseudo random function Rand
[FFH] little bear driver calling process (take calling LED light driver as an example)
Js7day (event object, event flow, event capture and bubble, prevent event flow, event delegation, student information table cases)
arcgis js 4. Add pictures to x map
随机推荐
Execute any method of any class through reflection
浏览器node事件循环
IPhone 6 plus is listed in Apple's "retro products" list
The programmer and the female nurse went on a blind date and spent 360. He packed leftovers and was stunned when he received wechat at night
线性DP AcWing 897. 最长公共子序列
Less than three months after the programmer was hired, the boss wanted to launch the app within one month. If he was dissatisfied, he was dismissed immediately
Js6day (search, add and delete DOM nodes. Instantiation time, timestamp, timestamp cases, redrawing and reflow)
js1day(输入输出语法,数据类型,数据类型转换,var和let区别)
获取文件版权信息
JSON序列化 与 解析
趣味 面试题
包管理工具
Use MySQL events to regularly perform post seven world line tasks
FBX import under ue4/ue5 runtime
2.7 binary tree, post order traversal - [FBI tree]
This "little routine" is set on the dough cake of instant noodles. No wonder programmers are always hungry
Day12 control flow if switch while do While guessing numbers game
Deep Copy Event bus
There is a hidden danger in CDH: the exchange memory used by the process of this role is XX megabytes. Warning threshold: 200 bytes
Heap acwing 839 Simulated reactor