アルゴリズム道中記〜20240408〜

ぼくの学校の図書館に、鉄則本がありました。早速借りて、DPの問題を考えました。毎回、DPで挫折しているように気がするからです。

A16 - Dungeon 1（※初版第 1 刷の B22 も同じ問題です）

#include <bits/stdc++.h>
#define print(x) cout << x << endl;
#define rep(i, s, n) for (long long i = s; i < (long long)(n); i++)
using namespace std;
using ll = long long;

int main() {
  ll N;
  cin >> N;
  vector<ll> A(N), B(N);
  vector<ll> dp(N+1);
  rep (i, 2, N+1) cin >> A[i];
  rep (i, 3, N+1) cin >> B[i];
  dp[1] = 0;
  dp[2] = A[2];
  rep (i, 3, N+1)
    dp[i] = min(dp[i-1] + A[i], dp[i-2] + B[i]);
  print(dp[N]);
  return 0;
}

しかしながら、答えは同じであるのに、通りません。普通のカエル跳び問題だと思ったのですが… なんだかよくわかりませんので、今日のところは放置することにします。

明日は、ナップザックでも取り組もうかと思います。