CFR 446 A. DZY Loves Sequences ( DP )
Problem - A - Codeforces
題意:
給一個序列,修改至多一個元素,求最長可能的嚴格遞增序列長度。
解法:
預處理每個數至右最多能遞增多長,至左最多能遞減多長。接著枚舉改變的位子,更新答案。
int N; vi A; void init(){ cin >> N; A = vi( N ); for( int i = 0; i < N; ++i ) cin >> A[ i ]; } vi dpbegin; vi dpend; void preprocess(){ dpbegin = dpend = vi( N + 1 ); for( int i = 0; i < N; ++i ){ if( i == 0 or A[ N - i - 1 ] <= A[ N - i ] ) dpbegin[ i + 1 ] = dpbegin[ i ] + 1; else dpbegin[ i + 1 ] = 1; if( i == 0 or A[ i - 1 ] <= A[ i ] ) dpend[ i + 1 ] = dpend[ i ] + 1; else dpend[ i + 1 ] = 1; } } void solve(){ int ans = min( N, max( *max_element( dpbegin.begin(), dpbegin.end() ), *max_element( dpend.begin(), dpend.end() ) ) + 1 ); for( int i = 0; i < N; ++i ) if( i == 0 or i + 1 == N or A[ i - 1 ] <= A[ i + 1 ] ) upmax( ans, dpend[ i ] + 1 + dpbegin[ N - i - 1 ] ); cout << ans << endl; }