DP-LIS and LCS
2024-10-21 10:19:34
最长上升子串
f[i]=f[I-1]+1(f[I]>f[I-1])
f[I]=1;(f[I]<=f[I-1])
输出max(f(I))
最长上升子序列
f[I]=max(f[I],f[j]+1);
For example:D. Remove One Element http://codeforces.com/contest/1272/problem/D
左边扫一遍,右边扫一遍,然后好用
```c++
include<bits/stdc++.h>
using namespace std;
int Dpl[200010], a[200010], Dpr[200010];
int n;
int main()
{
cin >> n;
for (int i = 1;i <= n;++i)
cin >> a[i];
int ans = 1;
Dpl[1] = Dpr[n] = 1;
for (int i = 2;i <= n;++i)
{
if (a[i] > a[i-1])
Dpl[i] = Dpl[i-1]+1;
else
Dpl[i] = 1;
}
for (int i = n-1;i >= 1;--i)
{
if (a[i] < a[i+1])
Dpr[i] = Dpr[i+1]+1;
else
Dpr[i] = 1;
}
for (int i = 2;i <= n;++i)
{
ans = max(ans, Dpl[i]);
if (a[i] > a[i-2])
ans = max(ans, Dpl[i-2]+Dpr[i]);
}
cout << ans;
return 0;
}
最新文章
- C# 5.0 异步编程
- ASP.NET Core的配置(4):多样性的配置来源[中篇]
- 介绍一种基于gulp对seajs的模块做合并压缩的方式
- [Ubuntu] 转载-使用Ubuntu修复grub
- 【转】Entity Systems
- poj 2528 Mayor&#39;s posters(线段树)
- jersey post提交到 ContainerRequestFilter 而HttpServletRequest获取不到数据(转)
- node.js常用的几个模块总结
- ORA-14400: inserted partition key does not map to any partition
- 收集经常使用的.net开源项目
- Linux学习笔记(一)----Ubuntu下的apt命令
- python 时间段的随机日期输出
- BurpSuiteProxy安装使用
- 【深入Java虚拟机】一 JVM类加载过程
- linux 再多的running也挡不住锁
- swift - VC添加手势返回
- [Vue warn]: Invalid prop: custom validator check failed for prop ";xxx";.问题
- 深入理解JAVA虚拟机阅读笔记2——垃圾回收
- idea中添加模板。
- NYOJ 141 Squares (数学)