当前位置:网站首页>The longest ascending subsequence model acwing 1014 Mountaineering
The longest ascending subsequence model acwing 1014 Mountaineering
2022-07-07 14:13:00 【T_ Y_ F666】
Longest ascending subsequence model AcWing 1014. Mountaineering
Original link
Algorithm tags
DP linear DP Longest ascending subsequence
Ideas
Ask for i Ending ascending sequence , With i The reverse rising at the end is the descending sequence , With i It is a sequence in which the dividing point rises first and then falls , Find the maximum .
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 f[N], f1[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 n=read();
rep(i, 1, n+1){
a[i]=read();
}
int ans=0, ans1=0, ans2=0;
// With i Ending ascending sequence
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);
}
}
ans1=max(ans1, f[i]);
}
// With i The reverse rising at the end is the descending sequence
Rep(i, n, 0){
f1[i]=1;
Rep(j, n, i+1){
if(a[j]<a[i]){
f1[i]=max(f1[i], f1[j]+1);
}
}
ans2=max(ans2, f1[i]);
}
// Go up first Post descent sequence
rep(i, 1, n+1){
ans=max(ans, f[i]+f1[i]-1);
}
printf("%lld\n", max({ans, ans1, ans2}));
}
And y The general code is consistent
y Master code
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int h[N];
int f[N], g[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &h[i]);
for (int i = 0; i < n; i ++ )
{
f[i] = 1;
for (int j = 0; j < i; j ++ )
if (h[i] > h[j])
f[i] = max(f[i], f[j] + 1);
}
for (int i = n - 1; i >= 0; i -- )
{
g[i] = 1;
for (int j = n - 1; j > i; j -- )
if (h[i] > h[j])
g[i] = max(g[i], g[j] + 1);
}
int res = 0;
for (int i = 0; i < n; i ++ ) res = max(res, f[i] + g[i] - 1);
printf("%d\n", res);
return 0;
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
- UML sequence diagram (sequence diagram)
- 2022-7-7 Leetcode 844. Compare strings with backspace
- 一个简单LEGv8处理器的Verilog实现【四】【单周期实现基础知识及模块设计讲解】
- 请问,如图,pyhon云函数提示使用了 pymysql模块,这个是怎么回事?
- Redis 核心数据结构 & Redis 6 新特性详
- NDK beginner's study (1)
- IP address home location query
- Excuse me, when using Flink SQL sink data to Kafka, the execution is successful, but there is no number in Kafka
- 最长上升子序列模型 AcWing 1014. 登山
- [Reading stereo matching papers] [III] ints
猜你喜欢
最长上升子序列模型 AcWing 1012. 友好城市
Battle Atlas: 12 scenarios detailing the requirements for container safety construction
TPG x AIDU | AI leading talent recruitment plan in progress!
js 获取当前时间 年月日,uniapp定位 小程序打开地图选择地点
Did login metamask
Leecode3. Longest substring without repeated characters
Social responsibility · value co creation, Zhongguancun network security and Information Industry Alliance dialogue, wechat entrepreneur Haitai Fangyuan, chairman Mr. Jiang Haizhou
2022-7-7 Leetcode 844. Compare strings with backspace
2022-7-6 Leetcode 977. Square of ordered array
Details of redis core data structure & new features of redis 6
随机推荐
Laravel form builder uses
PHP中用下划线开头的变量含义
[network security] SQL injection syntax summary
Co create a collaborative ecosystem of software and hardware: the "Joint submission" of graphcore IPU and Baidu PaddlePaddle appeared in mlperf
gvim【三】【_vimrc配置】
call undefined function openssl_ cipher_ iv_ length
Take you to master the three-tier architecture (recommended Collection)
交换机和路由器的异同
mysql导入文件出现Data truncated for column ‘xxx’ at row 1的原因
Hands on Teaching: XML modeling
[AI practice] Application xgboost Xgbregressor builds air quality prediction model (II)
wpf dataGrid 实现单行某个数据变化 ui 界面随之响应
[high frequency interview questions] difficulty 2.5/5, simple combination of DFS trie template level application questions
Selenium库
参数关键字Final,Flags,Internal,映射关键字Internal
Laravel5 call to undefined function OpenSSL cipher IV length() error php7 failed to open OpenSSL extension
3D detection: fast visualization of 3D box and point cloud
請問,在使用flink sql sink數據到kafka的時候出現執行成功,但是kafka裏面沒有數
Reverse non return to zero code, Manchester code and differential Manchester code of common digital signal coding
Oracle advanced (V) schema solution