kmjp's blog

競技プログラミング参加記です

Codeforces #276 Div1 D. Kindergarten

いろんな解き方のある問題。
http://codeforces.com/contest/484/problem/D

問題

N要素の数列A[i]がある。
この数列を、任意個数の連続した部分列に分割したとき、個々の部分列のスコアは、部分列中の最大値と最小値の差となる。

部分列の総スコアを最大化せよ。

解法

以下の方法は自分の方法で、最短解はもっと相当短いので注意。

色々なやり方があるが、まずはどういうケースで最大化するか考えてみる。

  • 部分列は両端が最小値と最大値となるはずである。そうでなければ、その部分列は2つに分割した方が合計スコアが増える。
  • A[i]が局所的な最大値(A[i-1]<A[i]>A[i+1])または最小値(A[i-1]>A[i]<A[i+1])ならA[i-1]とA[i]とA[i+1]は同じ部分列に含まれることはない。A[i]は常に左右どちらかの部分列の端であり、同様にA[i-1]とA[i+1]のどちらかも部分列の端である。
  • 同じ数値が3つ以上続いても、その数字は2個以下の場合よりスコアは増えない。

上記推論より、自分はまずA[i]を次のように変換した。

  • 同じ数値が3個以上続いた場合、2個だけ残す。
  • 数値が5個以上連続して増加または減少するとき、最初の2つと最後の2個だけ残し真ん中は外す。上記推論より、局所的な最大値と最小値およびその隣接項以外は部分列の端に来ないためである。

この時点で、部分列の長さは4程度になるため、単純にDPしていけば良い。
上にも書いた通り、最短解はもっとはるかに短いので下記はあくまで参考。

int N;
ll dp[1000001];
vector<ll> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		if(V.size()>=2 && V.back()==x && V[V.size()-2]==x) continue;
		
		j=V.size()-1;
		if(V.size()>=4 &&
			(x>V[j]&&V[j]>V[j-1]&&V[j-1]>V[j-2]&&V[j-2]>V[j-3] ||
			 x<V[j]&&V[j]<V[j-1]&&V[j-1]<V[j-2]&&V[j-2]<V[j-3]))
			V[j-1]=V[j], V[j]=x;
		else V.push_back(x);
	}
	
	for(i=0;i<V.size();i++) {
		dp[i+1]=dp[i];
		for(j=1;j<=8;j++) if(i-j>=0)
			dp[i+1]=max(dp[i+1],dp[i-j]+*max_element(&V[i-j],&V[i+1])-*min_element(&V[i-j],&V[i+1]));
	}
	
	cout << dp[V.size()] << endl;
}

まとめ

自分のアイデアも悪くないとは思ったけど、最短解が短すぎる…。