読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0096

algorithm algorithm-動的計画法 contest contest-aoj language language-c++

4つの整数の和 | Aizu Online Judge
動的計画法を使ってやる
dp[i][j] = (i+1個の数を使って和jを実現する場合の数)
あとは適当に1000までという条件を組み込めばOK

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

typedef long long ll;

int main()
{
  int n;
  ll dp[4][4001]={};
  fill_n(dp[0],1001,1);
  FOR(i,1,3) REP(j,4001) FOR(k,0,min(j,1000)) dp[i][j] += dp[i-1][j-k];
  while(cin >> n) cout << dp[3][n] << endl;
  return 0;
}