181. Scuba diver
アルゴリズムをメモっといたら後で便利かもしれないと思った。*1
n本のシリンダーのから条件を満たすようにシリンダーをいくつか選ぶ。選んだシリンダーの重量の合計の最小値を求める問題。
条件: 選んだシリンダーに入っている酸素の量と窒素の量の合計が両方とも所定の量以上である。
メモ化で解く。
関数f(t, a, i)を次のように定義する。
0番目からi番目までのシリンダー(i番目を含む)が使用可能なとき、使用する各シリンダーの酸素と窒素の合計がそれぞれt, a以上になるようにシリンダーを選ぶときのシリンダーの重量の合計の最小値を返す。もしそのような選び方が存在しないなら∞を返す。*2
このようなfの実装を考える。
i番目のシリンダーの酸素の量、窒素の量、重量をそれぞれ ts[i], as[i], ws[i] とする。
まず i = 0 のとき、つまり使えるシリンダーがひとつしかないときは、次の3つの場合がある。
- 0番目のシリンダーを使わなくても条件を満たす場合。すなわち t = a = 0 の場合。このときは f(t, a, i) = 0
- 0番目のシリンダーを使えば条件を満たす場合。すなわち 1 <= t <= ts[0] かつ 1 <= a <= as[0] の場合。このときは f(t, a, i) = ws[0]
- 0番目のシリンダーを使っても条件を満たさない場合。すなわち t > ts[0] または a > as[0] の場合。このときは f(t, a, i) = ∞
次に 1 <= i < n のときを考える。
i番目のシリンダーに注目し、
- i番目のシリンダーを使わない場合
- i番目のシリンダーを使う場合
の2通りに分ける。
i番目のシリンダーを使わない場合、0からi-1番目までのシリンダーで t, a だけの窒素と酸素を供給しないといけないので、
f(t, a, i) = f(t, a, i - 1) (= w1 と置く)
i番目のシリンダーを使う場合、0からi-1番目までのシリンダーで残りの t - ts[i], a - as[i] だけの窒素と酸素を供給すればよいので、
f(t, a, i) = f(t - ts[i], a - as[i], i - 1) + ws[i] (= w2 と置く)
ただし、t - ts[i] や a - as[i] が負の数になるときは 0 として扱う。
この2つの場合のうち、良い方(値が小さい方)を最終的に選択する。すなわち
f(t, a, i) = min(w1, w2)
以上をコード化して、さらにメモ化するようにしたのが次のコード。(t = a = 0 かつ i >= 1 の場合の扱い方が上の説明と違うけど、i >= 1 でも f(0, 0, i) = 0 は成立するので大丈夫)
#include <stdio.h> #include <string.h> #define max(a, b) ((a) < (b) ? (b) : (a)) #define min(a, b) ((a) < (b) ? (a) : (b)) static const int M = 9999999; int ts[1000], as[1000], ws[1000]; int memo[22][80][1000]; int f(int t, int a, int i) { if (memo[t][a][i] != -1) { return memo[t][a][i]; } if (t == 0 && a == 0) { return (memo[t][a][i] = 0); } else { if (i == 0) { if (t <= ts[0] && a <= as[0]) return (memo[t][a][i] = ws[0]); else return (memo[t][a][i] = M); } else { int w1 = f(t, a, i - 1); int w2 = f(max(t - ts[i], 0), max(a - as[i], 0), i - 1) + ws[i]; return (memo[t][a][i] = min(w1, w2)); } } } int main() { int c; scanf("%d", &c); while (c--) { int t, a; scanf("%d%d", &t, &a); int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d%d%d", &ts[i], &as[i], &ws[i]); } memset(memo, -1, sizeof(memo)); printf("%d\n", f(t, a, n - 1)); } }
