原題鏈接：http://codeforces.com/problemset/problem/446/A
題意：給一個長度為n的序列，最多可以修改一個位置的數，求最長連續上升子序列。
題解：當a[i+1] > a[i-1]+2的時候，可以通過改變a[i]的值來使前后兩段合并，反之，分別考慮a[i]作為左邊那段最長的和右邊那段最長的。
#include <cstdio>
#include <cstring> #include <algorithm> #include <iostream> #include <vector> #include <set> #include <queue> #include <map> #include <cmath> 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