AOJ : 0557 - 1年生 (A First Grader)

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0557&lang=jp
日本語の問題文なので, 説明は省略します.

アルゴリズム

動的計画法で解けます.

[ 21 (計算の途中結果) ] [ N (数列の何項目か) ] = パターン数

となるように, DP表を作成して解きます.
DP表の, [数列の最後尾の数][N-1] が答えになります.

注意点

• 一項目の前には符号がつかないので注意.

プログラム

unsigned long long dp[102][22];

int main(void){
  int n;
  cin>>n;
  int t[n];

  for(int i=0;i<n;i++){
    cin>>t[i];
  }
  memset(dp,0,sizeof(dp));
  dp[1][t[0]] = 1;

  for(int i=1;i<n-1;i++){
    for(int j=0;j<=20;j++){
      if(dp[i][j] > 0){
        int plus = j + t[i];
        int minus = j - t[i];

        if(plus>=0 && plus<=20){
          dp[i+1][plus] += dp[i][j];
        }
        if(minus>=0 && minus<=20){
          dp[i+1][minus] += dp[i][j];
        }
      }
    }
  }
  cout<<dp[n-1][t[n-1]]<<endl;

  return 0;
}