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);
  }
};