mayoko’s diary

プロコンとかいろいろ。

yukicoder No.398 ハーフパイプ(2)

解法

dp します。

dp[i][mini][maxi][sum] = (i 番目までで最小値が mini, 最大値が maxi, 合計が sum になっているような場合の数)とします。

この dp は状態が O(6*W*W*6*W) で, 遷移に O(W) かかり, 結構計算量が多いですが, まぁ間に合います。

これが計算できれば, sum-mini-maxi == 4*X であるようなものをすべて数え上げるだけです。

const int MAX = 101;
ll dp[6][MAX][MAX][6*MAX];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    double X;
    cin >> X;
    for (int i = 0; i <= 100; i++)
        dp[0][i][i][i] = 1;
    for (int i = 1; i < 6; i++) for (int mini = 0; mini <= 100; mini++) {
        for (int maxi = mini; maxi <= 100; maxi++) for (int sum = i*mini; sum <= i*maxi; sum++) {
            if (!dp[i-1][mini][maxi][sum]) continue;
            for (int j = 0; j <= 100; j++) {
                dp[i][min(j, mini)][max(j, maxi)][sum+j] += dp[i-1][mini][maxi][sum];
            }
        }
    }
    int sum = 4*X;
    ll ans = 0;
    for (int i = 0; i <= 100; i++) for (int j = i; j <= 100; j++) {
        ans += dp[5][i][j][sum+i+j];
    }
    cout << ans << endl;
    return 0;
}