AOJ0557 A First Grader

0557.cpp

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define INF 1e+8
#define EPS 1e-8
#define PB push_back
#define rep(i,j) for(int i = 0; i < (j); i++)
#define reps(i,j,k) for(int i = j; i < k; i++)
using namespace std;
typedef long long ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
 
int n, N[101];
ll dp[101][101];	
int ans = 0;
/*
ll solve(int i, int wa){
	if(i == 0 && 0 <= wa && wa <= 20){
		if(N[0] == N[n]) return 1;
		else return 0;
	}
	if( wa == N[n]) return 1;
	else{
		if(0 <= wa+N[i+1] && wa+N[i+1] <= 20){
			return solve(i+1, wa+N[i+1]) + solve(i+1, wa-N[i+1]);
		}
		else{
			return 0;
		}
	}
}*/

ll solve(int i, int j){
	//cout<<"solve("<<i<<","<<j<<")\n";
	if(i == 1){
		if(j == N[n]){
			return 1;
		}else{
			return 0;
		}
	}else{
		ll res = 0;
		if( 0 <= j+N[n-i+1] && j+N[n-i+1] <= 20 ){
			if( dp[i-1][j+N[n-i+1]] == -1){
				dp[i-1][j+N[n-i+1]] = solve(i-1, j+N[n-i+1]);
			}
			res += dp[i-1][j+N[n-i+1]];
		}
		if( 0 <= j-N[n-i+1] && j-N[n-i+1] <= 20 ){
			if( dp[i-1][j-N[n-i+1]] == -1){
				dp[i-1][j-N[n-i+1]] = solve(i-1, j-N[n-i+1]);
			}
			res += dp[i-1][j-N[n-i+1]];
		}
		return res;
	}
}
 
int main(){
	cin>>n;	
	for(int i = 1; i <= n; i++){
		cin>>N[i];
	}
	rep(i,101) rep(j,101) dp[i][j] = -1;
	cout<<solve(n-1,N[1])<<endl;
	return 0;
}