AOJ Sum of Integers Ⅱ

改めてみると解けるようになっていたのでメモ

問題文

Aizu Online Judge

解法

をやります。
数字iを見ているときに、k個の数字を使っていて、和がjのときの場合の数
でも解けますが、
k個の数字を使ってていて、和がjの時の場合の数
としても解けます。dpの更新を後ろから行うと、異なる数字だけを使う数え上げができます。
参考になるかもしれない記事。

#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
signed main(){
    int n,s;
    auto dp = vectors(11,1001,0LL);

    dp[0][0] = 1;
    for(int num = 0; num <= 100;num++){
        for(int k = 9; k>= 0;--k){
            for(int crt = 0; crt <= 1000;crt++){
                if(dp[k][crt] != 0 and crt + num <= 1000){
                    dp[k+1][crt + num] += dp[k][crt];
                }
            }
        }
    }
    while(cin >> n >> s,n+s){
        cout << dp[n][s] << endl;
    }
}