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; }