当前位置:网站首页>最长上升子序列模型 AcWing 1014. 登山
最长上升子序列模型 AcWing 1014. 登山
2022-07-07 12:08:00 【T_Y_F666】
最长上升子序列模型 AcWing 1014. 登山
原题链接
算法标签
DP 线性DP 最长上升子序列
思路
分别求以i结尾上升序列,以i结尾反向上升即下降序列,以i为分割点先上升后下降序列,求最大值即可。
代码
#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;
// 以i结尾上升序列
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]);
}
// 以i结尾反向上升即下降序列
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]);
}
// 先上升 后下降序列
rep(i, 1, n+1){
ans=max(ans, f[i]+f1[i]-1);
}
printf("%lld\n", max({ans, ans1, ans2}));
}
与y总代码思路一致
y总代码
#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;
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
- Cargo placement problem
- Laravel5 call to undefined function OpenSSL cipher IV length() error php7 failed to open OpenSSL extension
- Getting started with cinnamon applet
- Getting started with MySQL
- Server to server (S2S) event (adjust)
- Ogre introduction
- Did login metamask
- 【网络安全】sql注入语法汇总
- 2022-7-6 初学redis(一)在 Linux 下下载安装并运行 redis
- 带你掌握三层架构(建议收藏)
猜你喜欢
随机推荐
Oracle advanced (V) schema solution
参数关键字Final,Flags,Internal,映射关键字Internal
带你掌握三层架构(建议收藏)
室内ROS机器人导航调试记录(膨胀半径的选取经验)
手把手教会:XML建模
为租客提供帮助
云计算安全扩展要求关注的安全目标和实现方式区分原则有哪些?
MySQL error 28 and solution
Redis can only cache? Too out!
2022-7-6 sigurg is used to receive external data. I don't know why it can't be printed out
Laravel5 call to undefined function OpenSSL cipher IV length() error php7 failed to open OpenSSL extension
【日常训练】648. 单词替换
Laravel form builder uses
Move base parameter analysis and experience summary
Build a secure and trusted computing platform based on Kunpeng's native security
SSRF漏洞file伪协议之[网鼎杯 2018]Fakebook1
供应链供需预估-[时间序列]
使用day.js让时间 (显示为几分钟前 几小时前 几天前 几个月前 )
2022-7-6 Leetcode27. Remove the element - I haven't done the problem for a long time. It's such an embarrassing day for double pointers
LeetCode简单题分享(20)