Codeforces #255 Div1 A. DZY Loves Sequences

本当は#FFだけどわかりにくいので#255で。
ABで若干無駄WAしてしまい、レート微減に。
http://codeforces.com/contest/446/problem/A

問題

N要素の数列A[i]が与えられる。
A[i]から真に単調増加となる最長の連続した部分列を作りたい。
ただし、A[i]のうち1要素のみ別の整数に値を変更できる。

最大何要素の部分列が作れるか。

解法

まず1度数列を見て、各要素から初めて何要素まで単調増加部分列を作れるかカウントする。
初期状態で全要素が単調増加なら、解は要素数と同じN。
それ以外の場合以下のいずれか大きい方が答え。

• 最長の単調増加部分列の前か後のいずれかの要素の値を変えると、長さを１追加できる。
• A[i-1]を終端とする部分列と、A[i+1]を始点とする部分列は、A[i-1]とA[i+1]に2以上の差があればA[i]をその中間値にすることで、2つの部分列を連結できる。

int N;
vector<int> V;

int dp[2][100001];

void solve() {
	int f,i,j,k,l,x,y;
	int ma=0;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		V.push_back(x);
	}
	
	dp[0][0]=dp[1][N-1]=1;
	FOR(i,N-1) dp[0][i+1]=(V[i]<V[i+1])?dp[0][i]+1:1;
	for(i=N-2;i>=0;i--) dp[1][i]=(V[i]<V[i+1])?dp[1][i+1]+1:1;
	FOR(i,N) ma=max(ma,dp[0][i]+1);
	FOR(i,N) ma=max(ma,dp[1][i]+1);
	for(i=1;i<N-1;i++) if(V[i-1]+2<=V[i+1]) ma=max(ma,dp[0][i-1]+1+dp[1][i+1]);
	
	ma=min(ma,N);
	cout << ma << endl;
	
}

まとめ

本番「連続した」を見落として無駄にLISを求めたりしてしまった…。