AOJ 0557 A First Grader
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557
解法
動的計画法
状態は
[i][j] = i番目の数字までを使ってjを作る+-の入れ方の総数
とした。
#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int a[101]; ll dp[101][21]; int main(){ int N, x; scanf("%d", &N); for(int i = 0; i < N-1; i++) scanf("%d", a + i); scanf("%d", &x); for(int i=0;i<100;i++)for(int j=0;j<21;j++) dp[i][j] = 0; dp[0][a[0]] = 1; for(int i = 1; i < N-1; i++){ int t = a[i]; for(int j = 0; j < 21; j++){ ll s = 0; if(j - t >= 0) s += dp[i - 1][j - t]; if(j + t <= 20) s += dp[i - 1][j + t]; dp[i][j] = s; } } printf("%lld\n", dp[N-2][x]); return 0; }