Let's Shoot! [Kodamanと愉快な仲間たち L]

https://www.hackerrank.com/contests/kodamanwithothers/challenges/lets-shoot

解説

https://www.hackerrank.com/contests/kodamanwithothers/challenges/lets-shoot/submissions/code/1316478561

dpで解けそう。 添字も小さいし、こんなDPで解けるんじゃない？ dp[i][mizu][hi][kusa] := i番目の生徒まで終わっていて、トレーニング済みの水属性がmizu人、火属性がhi人、草属性がkusa人のときのコスト最小値 80⁴なので、大丈夫そう。 根性DP。

int N, K, T[80], C[80];
int dp[81][82][82][82];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> T[i] >> C[i];

    rep(i, 0, N + 1) rep(mizu, 0, N + 1) rep(hi, 0, N + 1) rep(kusa, 0, N + 1) dp[i][mizu][hi][kusa] = inf;
    dp[0][0][0][0] = 0;

    rep(i, 0, N) rep(mizu, 0, N + 1) rep(hi, 0, N + 1) rep(kusa, 0, N + 1) if(dp[i][mizu][hi][kusa] < inf) {
        chmin(dp[i + 1][mizu][hi][kusa], dp[i][mizu][hi][kusa]);

        if (T[i] == 1) { // mizu
            chmin(dp[i + 1][mizu + 1][hi][kusa], dp[i][mizu][hi][kusa] + C[i]);
        } else if (T[i] == 2) { // hi
            if (mizu < hi + 1)
                continue;
            chmin(dp[i + 1][mizu][hi + 1][kusa], dp[i][mizu][hi][kusa] + C[i]);
        } else { // kusa
            if (hi < kusa + 1)
                continue;
            chmin(dp[i + 1][mizu][hi][kusa + 1], dp[i][mizu][hi][kusa] + C[i]);
        }
    }

    int ans = inf;
    rep(mizu, 0, N + 1) rep(hi, 0, N + 1) rep(kusa, 0, N + 1) if(mizu + hi + kusa == K) chmin(ans, dp[N][mizu][hi][kusa]);

    if (ans != inf) cout << ans << endl;
    else
        cout << "Let's Shoot!" << endl;
}