Div2の問題だけど、Div1 Easyと同じような問題でこちらの方が難しそうなので試してみた。
http://community.topcoder.com/stat?c=problem_statement&pm=11810
先のDiv1 Easyと似た問題。
n<=50、h[0]=h[n]=0と条件が緩和された一方、求めるのは到達可否だけじゃなくて到達方法の組み合わせ数。
最初は、通るべきパターンを1か所に置き、そのパターンに入るまでとパターンの後の数を掛けて累積したが、それだと数が大きすぎてダメだった。
というのも、パターンを2回以上通るケースを二重にカウントしてしまうため。
そこで戦略を変更。
まず、パターンのうちi文字目までたどったとき、次にUまたはDが来たとき、パターンの何文字目にくるかの遷移図(下記trans)を作る。
パターンが"UUUDUUUDD"なら、7文字目までたどったときに8文字目が"D"なら8、"U"なら5("UUUDUUUDU"はパターンの先頭8文字と一致しないが、最後5文字の"UUUDU"はパターンの先頭5文字に一致するから)
1回パターンをたどりきってしまえば、あとはUでもDでもパターンを辿りきった状態を繰り返す。
あとは、たどった数列の数・パターンの文字数・現在の高さ、の3つの要素でDPする。
最後に高さが0で、かつパターンを辿りきった数を答える。
class FoxAndMountain { public: int trans[51][2]; int memo[51][51][51]; static const int mo=1000000009; int count(int n, string history) { int hl, mind,h,i,j,k,res; char tstr[51]; char sstr[51]; hl = history.size(); strcpy(sstr,history.c_str()); ZERO(trans); FOR(i,hl) { //_P("%d %d\n",trans[i][1],trans[i][0]); ZERO(tstr); memmove(tstr,history.c_str(),i); if(history[i]=='U') { trans[i][1]=i+1; tstr[i]='D'; for(j=1;j<=i;j++) { if(memcmp(sstr,&tstr[i-(j-1)],j)==0) trans[i][0]=j; } } else { trans[i][0]=i+1; tstr[i]='U'; for(j=1;j<=i;j++) { if(memcmp(sstr,&tstr[i-(j-1)],j)==0) trans[i][1]=j; } } } trans[hl][0]=trans[hl][1]=hl; ZERO(memo); memo[0][0][0]=1; FOR(i,n) { FOR(j,26) { FOR(k,hl+1) { if(memo[i][j][k]==0) continue; if(j>0){ memo[i+1][j-1][trans[k][0]] += memo[i][j][k]; memo[i+1][j-1][trans[k][0]] %= mo; } if(j<25) { memo[i+1][j+1][trans[k][1]] += memo[i][j][k]; memo[i+1][j+1][trans[k][1]] %= mo; } } } } return memo[n][0][hl]; } }