Algoogle

Algorithm for Programming Contest

AOJ 0096 Sum of 4 Integers II

Category: AOJ Tag: dp

Sum of 4 Integers II

問題概要


[0,1000]の範囲の整数a, b, c, dの組のうち となる組の数を求めよ

解法


前計算でDPすればよい.
dp[i][j] := i個の0以上1000以下の整数の組で値jにする場合の数
dp[1][j] = 1
あとはこれを掛け合わせて以下のうように更新すれば良い
dp[2*i][j+k] += dp[i][j]*dp[i][k]

コード


(0096.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int dp[8][4096], n;

int main()
{
        for (int i = 0; i <= 1000; i++) dp[1][i] = 1;
        for (int i = 1; i < 3; i++)
                for (int j = 0; j <= 1000*i; j++)
                        for (int k = 0; k <= 1000*i; k++)
                                dp[i*2][j+k] += dp[i][j]*dp[i][k];

        while(cin >> n) cout << dp[4][n] << endl;
        return 0;
}

Comments