SRM401 Div.1 Easy FIELDDiagrams

問題

整数nが与えられる。
0,1,...,n-1行にそれぞれn-1,n-2,...1個のスペースがあるとし、左詰めで箱を詰める。
ただし、i行目の箱の数a_はa_i>a_j(i

方針

要は下に行くほど少なくなっていけばよい。
n-1行は0個か1個なので

dp[0][0] = 1;
dp[0][1] = 1;

とする。

dp[i][j] = sum(dp[i-1][0], dp[i-1][1] ... dp[i-1][j-1])

としてDPテーブルを更新していけばよい。

• >Passed System Test 219.42pts

実際には配るDPで実装した。

以下ソースコード

    long long countDiagrams(int n) {
        ll dp[n+2][n+2],ret=0;
        memset(dp, 0, sizeof(dp));

        dp[0][0] = 1;
        dp[0][1] = 1;

        for(int i=0;i<n-1;i++){
            for(int j=0;j<=i+1;j++){
                for(int k=j;k<=i+2;k++){
                    dp[i+1][k] += dp[i][j];
                }
            }
        }
        for(int i=1;i<=n;i++){
            ret += dp[n-1][i];
        }
        return ret;
    }