Codeforces 268D (164D) Wall Bars

問題

1234からなる長さnの文字列で、
1, 2, 3, 4のうちどれか一つ以上が、

• 文字列の先頭からh以内に現れ、
• 直前の同じ数字から常にh以内にもう一度現れ
• n - h番目以降に現れている

ようなものの数を求めよ。

制約条件

n≦1000
h≦min(30, n)

方針

1, 2, 3, 4が前回に出てきたときの位置を記憶するDP
hより離れてしまった文字はh + 1とかにしておけばよい。

dp[1の距離][2の距離][3の距離][4の距離]とするとTLEなので、
一つも距離h + 1以上のものがないときは、
（一つ目は1に決まっているので）３つの距離のみを覚えるとしたら通った。

ソースコード

const int mod = (int)1e9 + 9;
int n, h;
int dp[2][2][32][32][32];
int step[2][32][32][32][4][4];

void solve(int n, int h){
	int cur = 0, next = 1;
	int ans = 0;
	dp[cur][0][0][0][0] = 1;
	rep(i, n + 1){
		memset(dp[next], 0, sizeof(dp[next]));
		rep(j, 2) rep(a, h + 2) for(int b = a; b < h + 2; b++) for(int c = b; c < h + 2; c++){
			
			int &cnt = dp[cur][j][a][b][c];
			if(i >= n){
				(ans += cnt) %= mod;
				continue;
			}
			if(cnt == 0) continue;
			
			rep(k, 4) if(step[j][a][b][c][k][0] >= 0){
				int *p = step[j][a][b][c][k];
				dp[next][p[0]][p[1]][p[2]][p[3]] += cnt;
				if(dp[next][p[0]][p[1]][p[2]][p[3]] >= mod) dp[next][p[0]][p[1]][p[2]][p[3]] -= mod;
			}
		}
		swap(cur, next);
	}
	cout << ans << endl;
}

int main(){
	cin >> n >> h;
	rep(j, 2) rep(a, h + 2) for(int b = a; b < h + 2; b++) for(int c = b; c < h + 2; c++){
		vi v;
		v.pb(a + 1); v.pb(b + 1); v.pb(c + 1);
		if(j == 0) v.pb(1);
		else v.pb(h + 1);
		
		
		rep(k, 4) v[k] = min(v[k], h + 1);
		rep(k, 4){
			vi nv = v;
			int *p = step[j][a][b][c][k];
			if(v[k] <= h) nv[k] = 0;
			sort(all(nv));
			
			if(nv[0] >= h) p[0] = -1;
			else if(nv[3] < h){
				p[0] = 0;
				p[1] = nv[1];
				p[2] = nv[2];
				p[3] = nv[3];
			}
			else{
				p[0] = 1;
				p[1] = nv[0];
				p[2] = nv[1];
				p[3] = nv[2];
			}
		}
	}
	solve(n, h);
	return 0;
}