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;
}