この問題は割とあっさり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11767
問題
数値N,M,Kが与えられる。
1~N番の頂点が並んでいるので、この時M本の辺を張ったグラフを作りたい。
この時、以下の条件を満たすグラフの数を求めよ。
- 各辺が結ぶ2頂点は、数値の差がK以下であること。
- 各頂点に張られる辺の数は偶数であること。
解法
Kが小さいことを利用して、近傍K頂点の辺の偶奇をbitmapで保持してDPすればよい。
DPの状態は[今の頂点番号][残り辺の数][今より先K個先までの頂点の辺の偶奇]でN*M*2^K通りである。
実際はDPを2回行う。
1回目で、「今からi番目までの頂点の間にある本数の辺を張ったときにあるbitmapを生成する組み合わせ」を計算する。
2回目で、1回目の結果を使って[今の頂点番号][残り辺の数][今より先K個先までの頂点の辺の偶奇]を計算する。
1回目はO(N*M*K*2^K)、2回目はO(N*M^2*2^K)。
N,M,Kはあまり大きくないので十分終わる。
ll mo=1000000007; ll dpdp[31][31][1<<8]; ll dp1[9][31][1<<8]; class DengklekBuildingRoads { public: int numWays(int N, int M, int K) { int i,x,y,mask,mask2; ZERO(dp1); dp1[0][0][0]=1; FOR(i,K) { FOR(x,31) FOR(y,31) if(x+y<=M) { FOR(mask,1<<K) { dp1[i+1][x+y][mask ^ ((y%2)<<i)] += dp1[i][x][mask]; dp1[i+1][x+y][mask ^ ((y%2)<<i)] %= mo; } } } ZERO(dpdp); dpdp[0][M][0]=1; FOR(i,N) { int l = min(K,N-i-1); FOR(mask,1<<K) FOR(y,M+1) if((mask%2)==(y%2)) { for(x=y;x<=M;x++) if(dpdp[i][x][mask]) { FOR(mask2,1<<l) if(dp1[l][y][mask2]) { dpdp[i+1][x-y][mask2 ^ (mask>>1)] += dpdp[i][x][mask] * dp1[l][y][mask2]; dpdp[i+1][x-y][mask2 ^ (mask>>1)] %= mo; } } } } return dpdp[N][0][0]; } };
まとめ
割とオーソドックスなDP問題。