TopCoder SRM 263 Div1 Medium HardDequeSort

問題

双方向キューをいくつか使って、与えられた数列を次のようにソートする。
数列の先頭から項を見ていき、

• すでにある双方向キューどれかの先頭にその項を追加する
• すでにある双方向キューどれかの末尾にその項を追加する
• 新しい双方向キューを作り、その唯一の要素をその項とする

の操作を繰り返し、
最後に双方向キューを好きな順番に組み合わせて、一つの列にする。

結果の列がソートされているためには、最低でいくつの双方向キューを作らなければならないか、求めよ。

制約条件

-1000≦数列の各項≦1000
数列の項数≦50

方針

自分がやったのは、以下のようなO(n^3)のDP.
dp[l][r]を、数列のうち、l番目以上r番目未満の項だけを取り出したものソートするのに必要なキューの数の最小値とする。

l番目以上r番目未満の項だけを取り出したものが、一つのキューだけでつくれるなら1を返す。
無理なら、dp[l][i]+dp[i][r]に分割する。
全ての分割の仕方を試せばいい。

ソースコード

int n,d[52],v[52];
int dp[52][52];

bool ck(vi &v){
	int n=v.size(), b, s;
	b=s=v[0];
	rep(i,n){
		if(s<v[i]&&v[i]<b)return 0;
		s=min(s,v[i]); b=max(b,v[i]);
	}
	return 1;
}
int rec(int l,int r){
	int &res=dp[l][r];
	if(res>=0)return res;
	
	vi tmp;
	rep(i,n)if(v[l]<=d[i]&&d[i]<=v[r-1])tmp.pb(d[i]);
	if(ck(tmp))return res=1;
	
	res=inf;
	for(int i=l+1;i<r;i++)res=min(res,rec(l,i)+rec(i,r));
	return res;
}

class HardDequeSort {
	public:
	int minDeques(vector <int> data) 
	{
		n=data.size();
		rep(i,n)d[i]=v[i]=data[i];
		sort(v,v+n);
		memset(dp,-1,sizeof(dp));
		return rec(0,n);
	}
};