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

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0097

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

整数の和 | Aizu Online Judge
動的計画法を用いてやる.
dp[i][j] := (i個の異なる0〜100の数を用いて和jを実現する場合の数)
あとは0〜100まで順に更新する.
ここでポイントはdp[i][j]の更新の順序で必ずiについて逆順で更新しなければならない.
なぜならば0+0+9=9,0+1+1=2のように同じ数の連続の重複を許した場合の数になるためである.
この点に少し戸惑った.

#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++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)

using namespace std;

typedef long long ll;

int main()
{
  ll dp[11][1001]={};
  dp[0][0] = 1;
  FOR(k,0,100) DOWN(i,10,1) FOR(j,k,1000)
    dp[i][j] += dp[i-1][j-k];
  int n, s;
  while(cin>>n>>s,n) cout << dp[n][s] << endl;
  return 0;
}