SRM412 ForbiddenStrings

問題文
'A', 'B', 'C' のみの文字を用いて、長さ n の文字列が構成される。文字列のうち、その部分文字列において 'A', 'B', 'C' の文字が順不同で１つずつ連続しているようなものがあるものは、禁止文字列と定義する。禁止文字列でない長さ n の文字列の総数を答えよ。

解法

dp[文字数][1つ前の文字種][2つ前の文字種] := 禁止文字列の数

として、DPする。

class ForbiddenStrings {
public:
  long long countNotForbidden(int n) {
    if(n == 1) return 3;
    if(n == 2) return 9;
    long long dp[n+1][3][3];
    memset(dp, 0, sizeof dp);
    
    for(int i=0; i<3; i++)
      for(int j=0; j<3; j++)
        dp[2][i][j] = 1;

    for(int i=3; i<=n; i++)
      for(int j=0; j<3; j++)
        for(int k=0; k<3; k++)
          for(int l=0; l<3; l++) {
            if(((1<<j)|(1<<k)|(1<<l)) == (1<<3)-1) continue;
            dp[i][j][k] += dp[i-1][k][l];
          }
    
    long long sum = 0;
    for(int i=0; i<3; i++)
      for(int j=0; j<3; j++)
        sum += dp[n][i][j];
    
    return sum;
  }
};