0w1

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;
}