118D - Caesars Legions

Codeforces

問題

シーザーは兵士を整列させるのが大好きで、n1人の歩兵とn2人の騎兵を所有しています。彼にはこだわりがあって、k1人より多く歩兵が連続して並んでいたり、k2人より多く騎兵が連続して並んでいるのは、美しくない並び方だと思っています。n1,n2,k1,k2が与えられたとき、シーザーが美しいと思う並べ方の総数を答えなさい。(n1,n2<=100 k1,k2<=10)

解法

dp[n][m][k][l]:=「歩兵をn人,騎兵をm人使って,最後にl人の(歩兵(k=0)or騎兵(k=1))が連続するような並べ方の総数」
と定義すると

  • dp[n+1][m][0][0] = Σdp[n][m][1][l] (l=0,...,k2-1) (1が並んでいるところに0を追加する。)
  • dp[n][m+1][1][0] = Σdp[n][m][0][l] (l=0,...,k1-1) (0が並んでいるところに1を追加する。)
  • dp[n+1][m][0][l+1] = dp[n][m][0][l] (0が並んでいるところに0を追加する)
  • dp[n][m+1][1][l+1] = dp[n][m][1][l] (1が並んでいるところに1を追加する)

が成り立つので、ループを使って計算する。
答えは Σdp[n1][n2][k][l]

コード

int main(){
  int n1,n2,k1,k2;
  cin>>n1>>n2>>k1>>k2;
  int dp[102][102][2][11]={};
  dp[1][0][0][0] = 1;
  dp[0][1][1][0] = 1;
  FOR(i,0,n1+1)FOR(j,0,n2+1)REP(k,10){
    dp[i+1][j][0][0] += dp[i][j][1][k];
    dp[i][j+1][1][0] += dp[i][j][0][k];
    if(k+2 <= k1)dp[i+1][j][0][k+1] += dp[i][j][0][k];
    if(k+2 <= k2)dp[i][j+1][1][k+1] += dp[i][j][1][k];
    dp[i+1][j][0][0] %= MOD;
    dp[i][j+1][1][0] %= MOD;
    dp[i+1][j][0][k+1] %= MOD;
    dp[i][j+1][1][k+1] %= MOD;
  }
  int ans = 0;
  REP(i,2)REP(j,10)ans = (ans+dp[n1][n2][i][j])%MOD;
  cout<<ans<<endl;
  return 0;
}