問題
http://community.topcoder.com/stat?c=problem_statement&pm=8480&rd=13503
A,B,Cからなる文字列がある。
ただし、AとBとCが連続して３つ並ばないようにしたい。
文字列の長さnが与えられたとき、そのような文字列の総数を求める。
解き方
dpで解けそうな問題。
前の状態として直前２つの文字が何であったか覚えていればよいので、
dp[現在位置][２つ前までのAの有無][２つ前までのBの有無][２つ前までのCの有無]
としてあげればよい。
コード
class ForbiddenStrings {
public: long long countNotForbidden(int n) {
long long dp[n+1][4][4][4];
memset(dp,0,sizeof(dp));
dp[0][0][0][0]=1;
FORE(i,0,n)FORE(j,0,4)FORE(k,0,4)FORE(l,0,4){
int nextj=(j&1)<<1;
int nextk=(k&1)<<1;
int nextl=(l&1)<<1;
if(!(k && l))dp[i+1][nextj|1][nextk][nextl]+=dp[i][j][k][l];
if(!(j && l))dp[i+1][nextj][nextk|1][nextl]+=dp[i][j][k][l];
if(!(j && k))dp[i+1][nextj][nextk][nextl|1]+=dp[i][j][k][l];
}
long long ret=0;
FORE(i,0,4)FORE(j,0,4)FORE(k,0,4)ret+=dp[n][i][j][k];
return ret;
}
};
public: long long countNotForbidden(int n) {
long long dp[n+1][4][4][4];
memset(dp,0,sizeof(dp));
dp[0][0][0][0]=1;
FORE(i,0,n)FORE(j,0,4)FORE(k,0,4)FORE(l,0,4){
int nextj=(j&1)<<1;
int nextk=(k&1)<<1;
int nextl=(l&1)<<1;
if(!(k && l))dp[i+1][nextj|1][nextk][nextl]+=dp[i][j][k][l];
if(!(j && l))dp[i+1][nextj][nextk|1][nextl]+=dp[i][j][k][l];
if(!(j && k))dp[i+1][nextj][nextk][nextl|1]+=dp[i][j][k][l];
}
long long ret=0;
FORE(i,0,4)FORE(j,0,4)FORE(k,0,4)ret+=dp[n][i][j][k];
return ret;
}
};