TopCoder SRM 428 Div1 Easy TheLuckyString
問題
文字列がlucky stringであるとは、
連続するどの二文字も同じでないような文字列のことを言う。
与えられた文字列の文字を並べ替えた文字列で、lucky stringであるものはいくつあるか求めよ。
制約条件
文字列の長さ≦10
方針
next_permutationを使って全列挙できる。
DPでもできる。
dp[mask][last]を、最後の文字がlastで、使った文字の集合がmaskであるような状態の場合の数とする。
これを一文字ずつ更新するようなDPをすればよい。
自分はnext_permutationで計算量が間に合わないと何故か思い込んで、
"n回出てくる文字が何種類あるかを状態とする"ような再帰で解いた。
ソースコード
int n; int cnt[256], c[11]; int dfs(int cur,int prev){ if(cur==n)return 1; int ret=0; rep(i,11)if(i&&c[i]){ c[i]--; c[i-1]++; ret+=(c[i]+(prev!=i))*dfs(cur+1,i-1); c[i]++; c[i-1]--; } return ret; } class TheLuckyString { public: int count(string s) { memset(cnt,0,sizeof(cnt)); memset(c,0,sizeof(c)); n=s.size(); rep(i,n)cnt[s[i]]++; rep(i,256)if(cnt[i])c[cnt[i]]++; return dfs(0,-1); } };