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の数字を記憶する。何を展開して漸化式を立てるか、という問題は、もともと少ない自由度をわざわざ大きくする、という点で発想的だよなー。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #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;} |