four tea [Hokkaido University Programming Contest 2019 Day 1 A]

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/A

解説

https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3745829

A問題でむずかしめ感じに見えるが、とりあえず全探索を考えてみよう。
パッケージを買う最大個数について考えてみると、最大N個であることがわかる。
よって、全状態を見るとO(N⁴)である。
N≦100なので、計算量はギリギリ大丈夫そう。

dfsを使うことで、重複順列を列挙できる。
作れるお茶の杯数を計算し、N以上であれば、それに必要な値段の最小値をとっていく。

int N, P[4], T[4];
//---------------------------------------------------------------------------------------------------
int ans = inf;
int cnt[4];
void dfs(int cu) {
    if (cu == 4) {
        int prize = 0;
        rep(i, 0, 4) prize += P[i] * cnt[i];
        int cha = 0;
        rep(i, 0, 4) cha += T[i] * cnt[i];

        if (N <= cha) chmin(ans, prize);

        return;
    }

    rep(i, 0, N + 1) {
        cnt[cu] = i;
        dfs(cu + 1);
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, 4) cin >> P[i];
    rep(i, 0, 4) cin >> T[i];

    dfs(0);
    cout << ans << endl;
}