解いた問題のソースコードと解説など。


POJ 1745 Divisibility

問題文

DP強化週間。

長さNの数列が与えられる。数字間を+か-で計算していき、
その結果がKで割り切れるか調べよ、という問題。

いかにもなDP。雪だるま式に書くより、メモ化再帰の方が直感的だった。他の人は雪だるま式に書いてるとこが多いみたい。
dp[i+1][j]:=(i番目までの数列の加減算をmod Kしてjになるか)のbool DP。再帰関数内でmodしたものがマイナスにならないように大きいKの倍数を足して再帰している。

以下ソース。けっこう時間ギリギリだった。

bool dp[10001][100];
int a[10000];

int N, K;

void dfs(int i, int m){
  m %= K;
  if(dp[i][m]) return;
  
  dp[i][m] = true;
  if(i == N) return;

  dfs(i + 1, m + a[i] + 10000 * K);
  dfs(i + 1, m - a[i] + 10000 * K);
}

int main(int argc, char **argv){
  memset(dp, false, sizeof(dp));
  cin >> N >> K;
  for(int i = 0; i < N; i++)
    cin >> a[i];

  dfs(0, 0);

  if(dp[N][0]) cout << "Divisible" << endl;
  else cout << "Not divisible" << endl;
  return 0;
}

最初、dp[i][m] = true;とif(i == N) return;を
逆に書いていたのでどうしても答えが合わなかった。

少しずつできるようになってきたと思う。やったー。

Get up! 明日のSUPER ST@R!