1年生 (A First Grader) 第１０回日本情報オリンピック 予選４

問題の概要

１桁の数字の羅列（2<=N<100）が与えられ、最後の数字の前に等号（＝）を、それ以外の数字と数字の間に（＋）か（－）を挿入します。
計算の途中で負になったり２０を超えたりする場合はエラーです。等号がなりたつ数を回答します。

入力例

11
8 3 2 4 8 7 2 4 0 8 8

出力例

10

bit全探索で書いてみた

最初、問題文をN<２０と勘違いしており、その前提でbit全探索で書いてみました。
当然N<100なのでオーバーフローしました。
小さなケースの部分点20点だけをもらいました。
更にいろいろ考えてみましたがうまい解法を思いつきません。

そもそも１個づつ数える方法では10e9を超えるような場合に間に合うはずがありません。

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N;
  int A[25];
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  
  int ans=A[N-1];
  int ck; 
  long long cnt=0;
  for(int i=0;i<(1<<(N-2));i++){
    //cout<<i<<endl;
    ck=A[0]; 
    for(int j=0;j<N-2;j++){
      if(i & (1<<j)){
        ck+=A[j+1];
      }
      else{
        ck-=A[j+1];
      }
      if(ck<0) break;   
      if(ck>20) break;
    }
    if(ck==ans){
      //cout<<i<<endl;
      cnt++;
    }
  }
  cout<<cnt<<endl;
  return 0;
}

DPで解ける？

解説を見るとDPでうまいこと解けるようです。
自分でも考えてみます。

（to be continued)