競プロ典型90問 008 - AtCounter（★4）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_h

解法

DPで解く。基本的な考え方はナップサック 問題と同じで、dp[i][j]:=i番目まで見て、状態jとなる個数の数え上げとする。
文字列t="atcoder"とした時、遷移先は以下の２通り。

• dp[i+1][j]+=dp[i][j]
• dp[i+1][j+1]+=dp[i][j] (if s[j] == t[j])

コード

mint dp[101010][8];

string t = "atcoder";
int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  dp[0][0] = 1;
  rep(i,n){
    rep(j,8){
      dp[i+1][j]+=dp[i][j];
      if(s[i]== t[j])dp[i+1][j+1]+=dp[i][j];
    }
  }
  cout<<dp[n][7].x<<endl;
  return 0;
}