Osmium_1008と時間旅行 [Kodamanと愉快な仲間たち G]

https://www.hackerrank.com/contests/kodamanwithothers/challenges/osmium1008-and-timetravel

前提知識

• 最大最小系DP（メモリ節約も）

解説

https://www.hackerrank.com/contests/kodamanwithothers/challenges/disastrous-gemini/submissions/code/1316476143

最短経路を見る問題である。 しかも、アメをなめるかなめないかの2択ということで、DP感がする。 これは経験なので頑張ってほしい。

DPだと思って考えると、以下のDPが思いつく。 dp[i][year] := i番目までの飴をなめていて今yearにいるときになめた飴の最小個数 これで4*10⁷状態あって、遷移はなめるかなめないかの2択なので、これで行けそうな感じがする。 ちょっと大きめなので、大事をとって添字iの部分はメモリ節約してある。 あと、yearは負の数を取る可能性があるので、0をbase=200000としておこう。

const int MA = 401010;
int N, K, A[101010];
char B[101010];
int dp[2][MA];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i] >> B[i];

    int base = 200000;
    rep(year, 0, MA) dp[0][year] = inf;
    dp[0][base + 2019] = 0;

    rep(_i, 0, N) {
        int i = _i % 2;
        int i2 = 1 - i;

        rep(year, 0, MA) dp[i2][year] = inf;

        rep(year, 0, MA) if (dp[i][year] < inf)
        {
            chmin(dp[i2][year], dp[i][year]); // don't eat

            int year2 = year;
            if (B[_i] == 'F')
                year2 += A[_i];
            else
                year2 -= A[_i];

            if (0 <= year2 and year2 < MA)
                chmin(dp[i2][year2], dp[i][year] + 1);
        }
    }

    int ans;
    if (dp[N % 2][K + base] == inf)
        ans = -1;
    else
        ans = dp[N % 2][K + base];
    cout << ans << endl;
}