1年生 (A First Grader)
コード

DP強化週間

num[j] = j項目の数字
a[i][j] = j個目までの数字を使ってAOJ君が計算可能な数式によって、iを作る時の場合の数

とすると、以下のような漸化式が立てられる。

a[j][i] = a[j + num[i]][i-1] (もしj + num[i] < 21なら) + a[j - num[i]][i-1] (もしj - num[i] >= 0)

i番目までで作れる0から20の数字を記憶する。何を展開して漸化式を立てるか、という問題は、もともと少ない自由度をわざわざ大きくする、という点で発想的だよなー。

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    int n;
    cin >> n;
    int num[101];
    for (int i = 0; i < n-1; i++) 
        cin >> num[i];
    int dest;
    cin >> dest;

    long long a[21][101] = {};
    a[num[0]][0] = 1;
    for (int i = 1; i < n-1; i++) 
        for (int j = 0; j < 21; j++) 
            a[j][i] += ((j + num[i] < 21) ? a[j + num[i]][i-1] : 0) + ((j - num[i] >= 0) ? a[j - num[i]][i-1] : 0);
    cout << a[dest][n-1-1] << endl;

    return 0;
}