AOJ 0557: A First Grader

動的計画法で解けます。引っかかる人はほとんどいないかもしれませんがコーナーケース(最初が0のとき)があります。

#include<iostream>
using namespace std;
typedef long long ll;

ll dp[100][21];
int data[100];

int main(){
	int n;
	cin>>n;
	for(int i = 0; i < n; i++){
		cin>>data[i];
	}
	
	dp[1][data[0]] = 1;
	for(int i = 1; i < n-1; i++){
		for(int j = 0; j <= 20-data[i]; j++){
			dp[i+1][j+data[i]] += dp[i][j];
		}
		for(int j = data[i]; j <= 20; j++){
			dp[i+1][j-data[i]] += dp[i][j];
		}
	}
	
	cout<<dp[n-1][data[n-1]]<<endl;
	return 0;
}