題目：click here

題意：求給定序列更改其中一個元素后的最長連續上升子序列的長度

分析：最長的連續子序列有2種，一種是嚴格上升(沒有更改元素)的長度加1，一種是兩段嚴格上升的加起來。

?

1 #include <bits/stdc++.h> 2 using namespace std; 3 #define F first 4 #define S second 5 #define pb push_back 6 #define power(a) ((a)*(a)) 7 #define ENTER printf("\n"); 8 typedef unsigned long long ll; 9 const int INF = 0x3f3f3f3f; 10 const double EPS = 1e-8; 11 const int M = 1e5+5; 12 13 int n, ret; 14 int a[M]; 15 int dps[M]; // dps[i]保存以i開頭的最長連續上升子序列 16 int dpe[M]; // dpe[i]保存以i結束的最長連續上升子序列 17 void solve() { 18 ret = dpe[0] = dps[n-1] = 1; 19 for( int i=1; i<n; i++ ) 20 if( a[i] > a[i-1] ) dpe[i] = dpe[i-1] + 1; 21 else dpe[i] = 1; 22 for( int i=n-2; i>=0; i-- ) 23 if( a[i] < a[i+1] ) dps[i] = dps[i+1] + 1; 24 else dps[i] = 1; 25 for( int i=0; i<n; i++ ) 26 if( a[i+1]-a[i-1] >= 2 ) ret = max( ret, dps[i+1]+dpe[i-1]+1 ); 27 else ret = max( ret, max( dps[i+1]+1, dpe[i-1]+1 ) ); 28 printf("%d\n", ret); 29 } 30 31 int main() { 32 while( ~scanf("%d", &n ) ) { 33 for( int i=0; i<n; i++ ) 34 scanf("%d", a+i); 35 solve(); 36 } 37 return 0; 38 }

?

轉載于:https://www.cnblogs.com/TaoTaoCome/p/4744539.html

總結

以上是生活随笔為你收集整理的CodeForces 447C DZY Loves Sequences DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。