yukicoder : No.209 Longest Mountain Subsequence

★２よりは難しいと思うけど、No.210よりは簡単だと思うんだよな。
http://yukicoder.me/problems/368

問題

N要素の整数列A[i]が与えられる。
N要素A[i]の部分列B[j]のうち、以下の条件を満たすものの最大長を求めよ。

KをBの要素数として、Bがある1≦j≦Kに対し

• B[1]～B[j]が真に単調増加
• B[j]～B[K]が真に単調減少
• (B[2]-B[1])、(B[3]-B[2])、...(B[j]-B[j-1])が真に単調増加
• (B[j+1]-B[j])、(B[j+2]-B[j+1])、...(B[K]-B[K-1])が真に単調減少

解法

B[j]を数列Bの頂点とする。
A[i]がそれぞれ頂点となる場合を総当たりし、左右のすそ野の長さの最大長を求める。

例えば、頂点B[j]の手前に最大何個要素が来るか考える。
left(L,R)を、B[x]=A[L], B[x+1]=A[R]がB[j]の手前にある場合、A[L]より手前の要素を何個Bに含められるかの最大値とする。

と計算できるので、メモ化再帰でO(N^3)で列挙できる。

B[j]の後の要素も、同様にright(L,R)を考えればよい。
A[i]を頂点とするBの最大長はとなる。

int T,N,A[1010];
int L[101][101];
int R[101][101];

int left(int LL,int RR) {
	int& ret=L[LL][RR];
	int x;
	if(ret<0) {
		ret=0;
		FOR(x,LL) if(A[x]<A[LL] && A[LL]-A[x]<A[RR]-A[LL]) ret=max(ret,left(x,LL)+1);
	}
	return ret;
}
int right(int LL,int RR) {
	int& ret=R[LL][RR];
	int x;
	if(ret<0) {
		ret=0;
		for(x=RR+1;x<N;x++) if(A[x]<A[RR] && A[RR]-A[x]<A[LL]-A[RR]) ret=max(ret,right(RR,x)+1);
	}
	return ret;
}

int dodo(int i) {
	int x;
	int lm=0,rm=0;
	
	// left side
	FOR(x,i) if(A[x]<A[i]) lm=max(lm,left(x,i)+1);
	// right side
	for(x=i+1;x<N;x++) if(A[x]<A[i]) rm=max(rm,right(i,x)+1);
	
	return lm+rm+1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	MINUS(L);
	MINUS(R);
	
	int ma=-1;
	FOR(i,N) ma=max(ma,dodo(i));
	cout<<ma<<endl;
}

まとめ

解法はすぐ思いついたけど、このDPは辛うじて★３かな。