TopCoder SRM 618 Div1 Medium LongWordsDiv1

Div2 Mediumのアレンジ問題。
うーん、500ptのMediumだけど解法にたどり着けず残念。
http://community.topcoder.com/stat?c=problem_statement&pm=13111

問題

以下の文字列を好ましい文字列とする。

1. 同じ文字が連続しない
2. ある２種類の文字x,yに対して、部分文字列としてxyxyを持たない
3. 上記２条件を満たす文字列のうち最長

Nが与えられたとき、N文字で構成できる好ましい文字列の組み合わせを求めよ。

解法

まず文字列長について、x種類の文字で構成できる条件を満たす文字列長はL(x)=2x-1である。
これには文字列の構成法を考えるとよい。
x=1,2の時はテストケースにあるとおりL(1)=1, L(2)=3である。

ここで、(x-1)種類の文字から構成される文字列に新たな文字aを加えてx種類の文字から文字列を構成することを考える。
この場合、最長となる組み合わせは次の２通りである。

1. 最初と最後をaとし、間を(x-1)種類の最長文字列を配置する。aXXXXXaの形。XXXXXの部分が2x-3文字なので全体は2x-1文字。
2. aXXXXaYYYYaのようにaを３回使う。XXXXとYYYYはそれぞれ同じ文字を使わず、1種類以上(x-1)種類以下の文字で構成される文字列を入れる。この際XXXX部とYYYY部の長さの和は2x-4文字なので、全体は2x-1文字
3. 他の形(aを1回や、先頭・末尾以外でaを２回使う)は2x-1文字を満たせないので対象外

あとは上記条件で漸化式を解けばよい。
x文字で構成できる条件を満たす文字列で、文字の種類を無視して文字の並び順だけ考えた組み合わせ数をP(x)とする。
P(0)=P(1)=P(2)=1で、x>=3ではを求めればよい。
後は文字の割り当て方法を掛けるだけ。O(N^2)で処理できる。

ll mo=1000000007;
ll dpdp[5001];

class LongWordsDiv1 {
	public:
	int count(int n) {
		ll ret;
		int i,j,N;
		
		ZERO(dpdp);
		dpdp[0]=dpdp[1]=dpdp[2]=1;
		
		for(i=3;i<=n;i++) {
			for(j=1;j<i;j++) dpdp[i]+=dpdp[j]*dpdp[i-1-j], dpdp[i]%=mo;
		}
		
		FOR(i,n) dpdp[n]=dpdp[n]*(i+1)%mo;
		return dpdp[n];
	}
};

まとめ

この最長文字列構成法が思いつかず簡単な漸化式に持っていけなかった。