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

先日に続いて１年生に挑戦です。

自分なりのDPで書いてみました。

WAになったコード

i番目の数まで足したときの値が０～２０の範囲なので、i番目までとそこまでの計算結果をｄｐの配列にしてみました。
足し算の結果の場合と引き算の結果の場合で遷移させたつもりです。

テストケース１は通りましたがテストケース２が合いません。

もう少し考えてみます。

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

int main(){
int N;
cin>>N;
long long DP[N+1][21];
long long A[N+1];
for(int i=1;i<=N;i++){
cin>>A[i];
}
DP[1][A[1]]=1;
for(int i=2;i<N;i++){
for(int j=0;j<=20;j++){
for(int k=0;k<=20;k++){
if(DP[i-1][k]+A[i]==j) DP[i][j]+=DP[i-1][k];
if(DP[i-1][k]-A[i]==j) DP[i][j]+=DP[i-1][k];
}
}
}
long long ans=0;
ans=DP[N-1][A[N]];
cout<<ans<<endl;
return 0;
}

ACしたコード

間違いに気づいて修正しACしました。

それまでの合計がKでA[i]を足したときにjになる場合に遷移させなければなりません。

if(k+A[i]==j) DP[i][j]+=DP[i-1][k];

WAしたコードではDPlカウントで演算していました。

if(DP[i-1][k]+A[i]==j) DP[i][j]+=DP[i-1][k];

ここを直して無事にACできました。

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

int main(){
  int N;
  cin>>N;
  long long DP[N+1][21]; 
  for(int i=0;i<=N;i++){
    for(int j=0;j<=20;j++){
      DP[i][j]=0;
    }
  }
  
  long long A[N+1];
  for(int i=1;i<=N;i++){
    cin>>A[i];
  }
  DP[1][A[1]]=1;
  for(int i=2;i<N;i++){
    for(int j=0;j<=20;j++){
      for(int k=0;k<=20;k++){
        if(k+A[i]==j) DP[i][j]+=DP[i-1][k];
        if(k-A[i]==j) DP[i][j]+=DP[i-1][k];
      }
    }
  }
  long long ans=0;
  ans=DP[N-1][A[N]];
  
  /*for(int i=1;i<=5;i++){
    for(int j=0;j<=5;j++){
      cout<<i<<" "<<j<<" "<<DP[i][j]<<endl;
    }
  }
  */

  cout<<ans<<endl;
  return 0;
}

感想

DPの応用範囲の広さに驚きです。
途中の演算結果が20までしかない、ということでDPを思いつけるようになりたいです。