続いてSRM554。Div2 HardはDiv1 Hardの制限を大幅に緩めた問題となっている。
http://community.topcoder.com/stat?c=problem_statement&pm=12164
問題
1x1x1の大きさの立方体を、幅2x奥行2を1段分として1段ずつ積んで直方体を作っていく。
この時、各立方体はC色のいずれかを持ち、また最大K組まで隣接する立方体が同じ色を持っていても良い。
1~H段の各直方体において、上記条件を満たす立方体の積み方の組み合わせを答えよ。
解法
C<=4なので、1段分4マスの色の組み合わせは4^4=256通り。
よって、DP[最上段の色の組み合わせ][同色の立方体の組数]と状態を取って1段ずつDPで組み合わせ数を求めていけばよい。
1段ごとに、現在最上段の色の組み合わせが256通り、その上の段に積む組みわせが256通り、同色の立方体の組数がK<=7通りなので、H<=47段分繰り返しても問題ない。
単純なDP問題だね。
ll mo=1234567891; ll dpdp[2][256][8]; class TheBrickTowerHardDivTwo { public: int find(int C, int K, int H) { ll tot=0; int mask,mask2,c[4],d[4],x,y,h; ZERO(dpdp); FOR(mask,256) { int n=0; c[0]=mask%4; c[1]=mask/4%4; c[2]=mask/16%4; c[3]=mask/64%4; if(c[0]>=C || c[1]>=C ||c[2]>=C ||c[3]>=C) continue; n=(c[0]==c[1])+(c[0]==c[2])+(c[1]==c[3])+(c[2]==c[3]); if(n<=K) { dpdp[0][mask][n]=1; tot++; } } for(h=1;h<H;h++) { int cur=(h-1)&1; int tar=h&1; ZERO(dpdp[tar]); FOR(mask,256) { c[0]=mask%4; c[1]=mask/4%4; c[2]=mask/16%4; c[3]=mask/64%4; if(c[0]>=C || c[1]>=C ||c[2]>=C ||c[3]>=C) continue; FOR(mask2,256) { d[0]=mask2%4; d[1]=mask2/4%4; d[2]=mask2/16%4; d[3]=mask2/64%4; if(d[0]>=C || d[1]>=C || d[2]>=C ||d[3]>=C) continue; int n=(d[0]==d[1])+(d[0]==d[2])+(d[1]==d[3])+(d[2]==d[3]); n+=(d[0]==c[0])+(d[1]==c[1])+(d[2]==c[2])+(d[3]==c[3]); FOR(x,K+1) if(n+x<=K) dpdp[tar][mask2][n+x] +=dpdp[cur][mask][x]; } } FOR(mask2,256) FOR(x,K+1) tot += dpdp[tar][mask2][x] %= mo; tot %= mo; } return (int)tot; } };
まとめ
さっきのSRM555といいそこまで手の込んでないDP問題だ。