AOJ 0557 - A First Grader
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557
JOI 2010予選 問題4
解法 :
DP
dp[i][j]:=i番目の数まで使って(足すか引くかして)jを作ることが出来る通りの数
※dp[0][0]=1で初期化した場合以下のコードではdp[1][0]=2となってしまうので注意
#include<iostream> using namespace std; long long dp[110][22]={0}; int main(){ int n; cin>>n; int a; cin>>a; dp[1][a]=1; //初期化 for(int i=2;i<n;i++){ int x; cin>>x; for(int j=0;j<21;j++){ if(j+x<21)dp[i][j+x]+=dp[i-1][j]; if(j-x>=0)dp[i][j-x]+=dp[i-1][j]; } } int c; cin>>c; cout<<dp[n-1][c]<<endl; }