TopCoder SRM 395 Div1 Medium Skyscrapers

問題

N個のビルが一列に並んでいて、それぞれの高さは1,2,3,...,Nである。
ビルiが左側から見えるとは、すべてのjiなるjについてh[j]

制約条件

N≦100

方針

メモ化再帰。
まずは最も高いビルの位置を決める。
これがi番目にあるとき、1〜i-1番目に見えるビルがleftSide-1個あり、i+1〜N番目に見えるビルがrightSide-1個ある。
左側にあるビルの選び方はC(N-1,i-1)通りである。

n個のビルのうち、k個のビルが見えているような並び方をf(n,k)とおくと、
この中で一番高いビルがi番目に来るとして、
f(n,k)=ΣC(n-1,i-1)*f(i-1,k-1)*(n-i)!
と表せるため、同じ問題のサイズが小さいものに帰着し、再帰により解ける。

二項係数C(n,k)はあらかじめ計算しておく。

ソースコード

ll P[101][101], C[101][101];
ll dp[101][101];
ll solve(int n,int k){
  if(n==k)return 1;
  if(n<k||k==0)return 0;
  
  ll &res=dp[n][k];
  if(res>=0)return res;
  
  res=0;
  for(int i=k;i<=n;i++)
    (res+=solve(i-1,k-1)*C[n-1][i-1]%mod*P[n-i][n-i]%mod)%=mod;
  
  return res;
}

class Skyscrapers {
  public:
  int buildingCount(int N, int leftSide, int rightSide) {
    memset(dp,-1,sizeof(dp));
    rep(i,101)rep(j,i+1)C[i][j]=i==0||j==i?1:(C[i-1][j-1]+C[i-1][j])%mod;
    rep(i,101)rep(j,101)P[i][j]=j?P[i][j-1]*(i-j+1)%mod:1;
    ll ans=0;
    for(int i=1;i<=N;i++)
      (ans+=C[N-1][i-1]*solve(i-1,leftSide-1)%mod*solve(N-i,rightSide-1)%mod)%=mod;
    
    return ans;
  }
};