DP Codeforces Round #FF (Div. 1) A. DZY Loves Sequences

题目传送门

 /*
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 ;
}
上一篇:【原创】kerberos无密码登录


下一篇:HDU1026 Ignatius and the Princess I