Codeforces Round #FF (Div. 1) A. DZY Loves Sequences-白红宇

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

阅读量：4308 次

发布时间：2019-06-06

本文共 770 字，大约阅读时间需要 2 分钟。

原题链接：http://codeforces.com/problemset/problem/446/A

题意：给一个长度为n的序列，最多可以修改一个位置的数，求最长连续上升子序列。

题解：当a[i+1] > a[i-1]+2的时候，可以通过改变a[i]的值来使前后两段合并，反之，分别考虑a[i]作为左边那段最长的和右边那段最长的。

#include 
    
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
            #include 
            
              using namespace std; typedef long long LL; int a[100001], dp[100001], r[100001]; int main() { a[0] = -1; int n; cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; dp[1] = 1; for(int i = 2; i <= n; i++) if(a[i] > a[i-1]) dp[i] = dp[i-1]+1; else dp[i] = 1; r[n] = n; for(int i = n-1; i >= 1; i--) { if(a[i] < a[i+1]) r[i] = r[i+1]; else r[i] = i; } int ans = 0; for