DP Codeforces Round #FF (Div. 1) A. DZY Loves Sequences
2024-08-30 21:47:31
/*
DP:先用l,r数组记录前缀后缀上升长度,最大值会在三种情况中产生:
1. a[i-1] + 1 < a[i+1],可以改a[i],那么值为l[i-1] + r[i+1] + 1
2. l[i-1] + 1 3. r[i+1] + 1 //修改a[i]
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std; const int MAXN = 1e5 + ;
const int INF = 0x3f3f3f3f;
int a[MAXN];
int l[MAXN], r[MAXN];
int n; int main(void) //Codeforces Round #FF (Div. 1) A. DZY Loves Sequences
{
scanf ("%d", &n); int ans = ;
for (int i=; i<=n; ++i)
{
scanf ("%d", &a[i]);
l[i] = ;
if (i > && a[i] > a[i-]) l[i] = l[i-] + ;
} for (int i=n; i>=; --i)
{
r[i] = ;
if (i < n && a[i] < a[i+]) r[i] = r[i+] + ;
} for (int i=; i<=n; ++i)
{
ans = max (ans, l[i]); ans = max (ans, r[i]);
if (i > && i < n && a[i-] + < a[i+]) ans = max (ans, l[i-] + r[i+] + );
if (i > ) ans = max (ans, l[i-] + );
if (i < n) ans = max (ans, r[i+] + );
} printf ("%d\n", ans); return ;
}
最新文章
- GridControl读取xml和保存xml
- ImageMagick之PDF转换成图片(image)
- python numpy 介绍
- Python Django 开发 2 数据库
- H - Ones
- Android学习资料整理
- Django REST FrameWork中文教程3:基于类的视图
- Spring通过注释配置Bean2 关联关系
- JavaScript我学之七数组
- ESP8266小知识与注意事项
- 关于RecyclerView你知道的不知道的都在这了(上)
- 通达OA批量处理没有结束但前台显示已经结束的流程
- 从零搭建ES搜索服务(一)基本概念及环境搭建
- Excel中substitute替换函数的使用方法
- bzoj千题计划233:bzoj 1304: [CQOI2009]叶子的染色
- elasticserach + kibana环境搭建
- linux 忘记登陆密码
- 【hdu1005】Number Sequence
- 配置wampserver 虚拟主机
- 2018HN省队集训