SRM 557 Div2 Hard "FoxAndMountain"
問題(超意訳)
'U'と'D'を同じ数だけ使って長さNの文字列を作る。
つまり'U'と'D'をそれぞれN/2個ずつ使うのだが、
文字列を作っていく途中で、'D'の数が'U'の数を上回ってはならない。
例)
UUDDUD おk
UDDUUD だめ UDDまで作った時にDがUより多くなってる。
また、'U''D'から成るキーワードが与えられる。
このキーワードを部分文字列として含むような文字列が、
何個できるかを返せ。
制約
1 <= 作る文字列の長さ、キーワードの長さ <= 50
カンニング(長時間ガン見)しつつのソースコード
const int MAX_N = 50; const int MOD = 1000000009; int dp[MAX_N+1][MAX_N+1][MAX_N+1]; int ne[MAX_N+1][2]; class FoxAndMountain { public: void add( int& i, int j ){ i += j; i %= MOD; } int count(int n, string history){ int m = history.length(); for( int i = 0; i < m; i++ ){ int go = 0, ng = 1; char c = 'U'; if( history[i] == 'U' ){ go = 1; ng = 0; c ='D'; } ne[i][go] = i+1; int t = 0; for( int j = i-1; j >= 0 && t == 0; j-- ){ if( history[j] != c ) continue; bool ok = true; for( int k = 1; k <= j; k++ ){ if( history[j-k] != history[i-k] ){ ok = false; break; } } if( ok ) t = j + 1; } ne[i][ng] = t; } ne[m][0] = ne[m][1] = m; memset( dp, 0, sizeof(dp) ); dp[0][0][0] = 1; for( int i = 0; i < n; i++ ){ for( int j = 0; j <= n; j++ ){ for( int k = 0; k <= m; k++ ){ if( j - 1 >= 0 ) add( dp[i+1][j-1][ne[k][0]], dp[i][j][k] ); if( j + 1 <= n ) add( dp[i+1][j+1][ne[k][1]], dp[i][j][k] ); } } } return dp[n][0][m]; } };