AOJ 0096 Sum of 4 Integers II

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0096

概要

nが与えられたとき、a + b + c + d = n
となる組み合わせ数を求めよ。

解法

全探索だと、1000^4 なので間に合わない。

DP[i個目][合計]で数え上げをする。

コード

#include <iostream>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)

int main()
{
    long long dp[4][4001] = {};
    REP(i, 1001) dp[0][i] = 1;
    for (int i = 1; i < 4; i++) {
        for (int j = 4000; j >= 0; j--) {
            for (int k = 0; k <= 1000; k++) {
                if (j - k < 0) break;
                dp[i][j] += dp[i - 1][j - k];
            }
        }
    }
    while (1) {
        int n;
        cin >> n;
        if (cin.eof()) break;
        cout << dp[3][n] << endl;
    }
    return 0;
}