Codeforces #336 Div1 B. Zuma

オリジナルのZumaというゲームとは違うルール？
http://codeforces.com/contest/607/problem/B

問題

整数列Aが与えられる。
そのうち回文をなす連続部分列を取り除き、残りを連結する、という作業を繰り返し、最終的にAの全要素を取り除きたい。
最小で何回回文を取り除けばよいか。

解法

A[L..R]を取り除ききる回数をDPなりメモか再帰で求めよう。

• A[L]==A[R]の場合、
  • L==RまたはL+1==Rなら1手で取り除ける。
  • それ以外の場合、A[(L+1)..(R-1)]を取り除く手数を求めると、A[L..R]もそれに一致する。A[(L+1)..(R-1)]を取り除く最後の1手の時同時にA[L],A[R]もその両端に連結して消せるので、追加の1手が必要ない。
• A[L]とA[R]の一致不一致に依らず、L≦X＜Rとなる各Xに対し、A[L..X]とA[(X+1)..R]をそれぞれ消したときの回数の和を求めその最小値を取る。

A[L]==A[R]であってもA[L..X]とA[(X+1)..R]をそれぞれ取り除くケースの方が総処理数が減る場合があるので注意。
自分もそれで1WAした。

int N;
int C[505];
int memo[505][505];

int hoge(int L,int R) {
	if(L>R) return 0;
	if(L==R) return 1;
	if(memo[L][R]>=0) return memo[L][R];
	int ret=1000;
	
	if(C[L]==C[R]) {
		if(L+1==R) ret=1;
		else ret=hoge(L+1,R-1);
	}
	for(int i=L;i<R;i++) ret=min(ret,hoge(L,i)+hoge(i+1,R));
	
	return memo[L][R]=ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>C[i];
	MINUS(memo);
	_P("%d\n",hoge(0,N-1));
}

まとめ

TDPCのiwiっぽいね。