n 日間、毎日お菓子を食べる。 i 日目にはお菓子をちょうど dᵢ 個食べなければならず、その日お店ではお菓子を一個 pᵢ 円で好きなだけ売っている。 お菓子を買う日はお店まで行かなければならず、いくつ買ってもその日に交通費 f 円が一回かかる。 お菓子を一つも買わない日はお店に行かないので、交通費はかからない。 お菓子はその日に食べてもよいし、冷蔵庫に入れておいて次の日以降に食べてもよい。 一日は、買う、食べる、冷蔵庫に入れる、の順に過ぎる。 その日食べて残ったお菓子はすべてその夜冷蔵庫に入れなければならず、冷蔵庫には多くても C 個しか入らない。 冷蔵庫に入れたお菓子は、一晩ごとに一個 h 円の保管料がかかる。 初日の朝にはお菓子が一つもない。 最後の日の夜にもお菓子が残っていれば冷蔵庫に入れ、保管料を払う。 n 日間決められた数をすべて食べるのに使うお金（お菓子代、交通費、保管料の合計）の最小値を出力せよ。
入力
一行目に n、C、h、f、二行目に p₁ … pₙ、三行目に d₁ … dₙ が空白区切りで与えられる。 1 ≤ n ≤ 500、0 ≤ C ≤ 500、0 ≤ h ≤ 1,000,000、0 ≤ f ≤ 1,000,000,000、1 ≤ pᵢ ≤ 1,000,000、0 ≤ dᵢ ≤ 1,000
出力
最も少ないお金を一つ
例 1 · stdin
4 3 1 8
2 9 9 3
2 2 2 1
stdout
49
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
状態は「その夜冷蔵庫に残した個数 s」（0 〜 C）です：best[s] = そうなるまでにかかった最も少ないお金。 朝に s 個あり、今日 b 個買って d 個食べ、夜に s2 個残すなら b = s2 + d − s で、道は二つです。 お店に行かなければ b = 0 なので s は s2 + d だけで（s2 + d ≤ C のときだけ）、お金は best[s2 + d] + s2·h です。 お店に行けばmin(best[s] − s·p) + (s2 + d)·p + f + s2·h で、min は s ≤ s2 + d の s についてです（s = s2 + d は買わずに交通費を払うことになりますが、前の道よりいつも高いので混ざっても構いません）。 s を一つずつ全部見ると一日に C² = 25 万回、500 日で 1 億 2,500 万回になり、Python・Craykon には遅すぎます。 s2 を 0 から増やすと見られる s の範囲も増えるだけなので、前から最小値を積み上げながら（low）一日を C 回で終えます。 答えは best[0] です — 最後の夜に残すとお金が増えるだけです。 例：初日に 2 円で 5 個買い（10 + 交通費 8）、2 個食べて 3 個（冷蔵庫いっぱい）を入れ（3）、二日目はお店に行かず 2 個食べて 1 個入れ（1）、三日目に 9 円で 2 個買い（18 + 8）、2 個食べて 1 個入れ（1）、四日目はお店に行きません — 49 円です。 四日目の値段 3 円のほうが安いですが、交通費 8 円を節約するために三日目に 9 円でもう一個買います。 落とし穴その一：交通費を忘れると 26 円になります — 交通費がなく冷蔵庫の上限と保管料だけのよくある解き方では通りません。 落とし穴その二：逆に毎日交通費を払う（お菓子を買わない日も）と間違えます — お店に行かない道を別に見る必要があります。 落とし穴その三：冷蔵庫を使わずその日その日に買うのも、「今までで最も安い値段 + 保管料」でいつも買う貪欲法も、冷蔵庫の上限と交通費を考えられないので間違えます — どの日の分を前もって買うか選ぶ必要があり、DP が要ります。 落とし穴その四：保管料を忘れたり、上限を食べる前に測ったり（s2 + d ≤ C）すると間違えます — その日食べるお菓子は冷蔵庫に入れません。 落とし穴その五：お金は交通費 500 × 10 億 + お菓子代 500 × 1,000 × 100 万 + 保管料 500 × 500 × 100 万 ≈ 1.25×10^12 まで行き、32 ビットの int（約 21 億）を超えます。 C・C++ は long long、Java・C# は long が必要で、Python の整数には上限がなく、JavaScript・TypeScript・Craykon の数は倍精度浮動小数点数で 2^53（約 9×10^15）まで正確なので、そのままで大丈夫です。 「まだなれない」を表す値も言語ごとに違います：Python float("inf")、JavaScript・TypeScript Infinity（Infinity − 数 も Infinity）、Java・C#・C・C++ は足しても引いてもあふれない大きな数（Long.MAX_VALUE / 4 など）を使って比較で除きます — MAX_VALUE そのものに足すとあふれて負の数になります。 Craykon には無限大がないので -1 を「なれない」とし、最小値がまだないことには なし を使います（なし で計算すると止まるので、low == なし || … のように先に聞きます）。
Pythonmain.py · 31 行
import sysdata = sys.stdin.read().split()n, cap, keep, fare = int(data[0]), int(data[1]), int(data[2]), int(data[3])price = [int(x) for x in data[4 : 4 + n]]eat = [int(x) for x in data[4 + n : 4 + 2 * n]]INF = float("inf")# best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈best = [0] + [INF] * capfor day in range(n): p, d = price[day], eat[day] # 오늘 아침 s개가 있고, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s # 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep # 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d) # 그래서 s <= s2 + d인 s 가운데 (best[s] - s * p)가 가장 작은 것만 알면 된다: s2를 늘리며 앞에서부터 최솟값을 쌓는다 new = [INF] * (cap + 1) low = INF # s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 s = 0 for s2 in range(cap + 1): while s <= cap and s <= s2 + d: if best[s] != INF: low = min(low, best[s] - s * p) s += 1 if low != INF: new[s2] = low + (s2 + d) * p + fare + s2 * keep if s2 + d <= cap: # 가게에 가지 않는 날: 차비가 없다 new[s2] = min(new[s2], best[s2 + d] + s2 * keep) best = new# 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다print(best[0])
JavaScriptmain.js · 30 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, cap, keep, fare] = data;const price = data.slice(4, 4 + n);const eat = data.slice(4 + n, 4 + 2 * n);// best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 number로 정확하다)let best = new Array(cap + 1).fill(Infinity);best[0] = 0;for (let day = 0; day < n; day++) { const p = price[day], d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 const next = new Array(cap + 1).fill(Infinity); let low = Infinity; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 let s = 0; for (let s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { low = Math.min(low, best[s] - s * p); // Infinity - 수 = Infinity라 따로 거르지 않아도 된다 s++; } next[s2] = low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = Math.min(next[s2], best[s2 + d] + s2 * keep); } } best = next;}// 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다console.log(best[0]);
TypeScriptmain.ts · 32 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, cap, keep, fare] = data;const price: number[] = data.slice(4, 4 + n);const eat: number[] = data.slice(4 + n, 4 + 2 * n);// best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 number로 정확하다)let best: number[] = new Array<number>(cap + 1).fill(Infinity);best[0] = 0;for (let day = 0; day < n; day++) { const p = price[day], d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 const next: number[] = new Array<number>(cap + 1).fill(Infinity); let low = Infinity; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 let s = 0; for (let s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { low = Math.min(low, best[s] - s * p); // Infinity - 수 = Infinity라 따로 거르지 않아도 된다 s++; } next[s2] = low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = Math.min(next[s2], best[s2 + d] + s2 * keep); } } best = next;}// 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다console.log(best[0]);
JavaMain.java · 51 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int cap = Integer.parseInt(st.nextToken()); long keep = Long.parseLong(st.nextToken()); long fare = Long.parseLong(st.nextToken()); long[] price = new long[n]; int[] eat = new int[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) price[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) eat[i] = Integer.parseInt(st.nextToken()); final long INF = Long.MAX_VALUE / 4; // 더하거나 빼도 넘치지 않을 만큼 큰 수 // best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long) long[] best = new long[cap + 1]; Arrays.fill(best, INF); best[0] = 0; for (int day = 0; day < n; day++) { long p = price[day]; int d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 long[] next = new long[cap + 1]; long low = INF; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF) low = Math.min(low, best[s] - s * p); s++; } next[s2] = low == INF ? INF : low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap && best[s2 + d] < INF) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = Math.min(next[s2], best[s2 + d] + s2 * keep); } } best = next; } // 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 System.out.println(best[0]); }}
C#Main.cs · 48 行
using System;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); int cap = int.Parse(first[1]); long keep = long.Parse(first[2]); long fare = long.Parse(first[3]); long[] price = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); int[] eat = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse); const long INF = long.MaxValue / 4; // 더하거나 빼도 넘치지 않을 만큼 큰 수 // best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long) var best = new long[cap + 1]; Array.Fill(best, INF); best[0] = 0; for (int day = 0; day < n; day++) { long p = price[day]; int d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 var next = new long[cap + 1]; long low = INF; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF) low = Math.Min(low, best[s] - s * p); s++; } next[s2] = low == INF ? INF : low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap && best[s2 + d] < INF) // 가게에 가지 않는 날: 차비가 없다 { next[s2] = Math.Min(next[s2], best[s2 + d] + s2 * keep); } } best = next; } // 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 Console.WriteLine(best[0]); }}
C++main.cpp · 45 行
#include <algorithm>#include <iostream>#include <limits>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, cap; long long keep, fare; std::cin >> n >> cap >> keep >> fare; std::vector<long long> price(n); std::vector<int> eat(n); for (auto& p : price) std::cin >> p; for (auto& d : eat) std::cin >> d; const long long INF = std::numeric_limits<long long>::max() / 4; // 더하거나 빼도 넘치지 않을 만큼 큰 수 // best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long long) std::vector<long long> best(cap + 1, INF); best[0] = 0; for (int day = 0; day < n; day++) { long long p = price[day]; int d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 std::vector<long long> next(cap + 1, INF); long long low = INF; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF) low = std::min(low, best[s] - s * p); s++; } if (low < INF) next[s2] = low + (s2 + d) * p + fare + s2 * keep; if (s2 + d <= cap && best[s2 + d] < INF) { // 가게에 가지 않는 날: 차비가 없다 next[s2] = std::min(next[s2], best[s2 + d] + s2 * keep); } } best = std::move(next); } // 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 std::cout << best[0] << '\n'; return 0;}
Cmain.c · 45 行
#include <stdio.h>#include <string.h>#define MAXN 500#define MAXC 500#define INF 1000000000000000000LL /* 더하거나 빼도 넘치지 않을 만큼 큰 수 */static long long price[MAXN];static int eat[MAXN];/* best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(1.25×10^12까지라 long long) */static long long best[MAXC + 1], next[MAXC + 1];int main(void) { int n, cap; long long keep, fare; if (scanf("%d %d %lld %lld", &n, &cap, &keep, &fare) != 4) return 0; for (int i = 0; i < n; i++) scanf("%lld", &price[i]); for (int i = 0; i < n; i++) scanf("%d", &eat[i]); for (int s = 0; s <= cap; s++) best[s] = INF; best[0] = 0; for (int day = 0; day < n; day++) { long long p = price[day]; int d = eat[day]; /* 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 */ long long low = INF; /* s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값 */ int s = 0; for (int s2 = 0; s2 <= cap; s2++) { while (s <= cap && s <= s2 + d) { if (best[s] < INF && best[s] - s * p < low) low = best[s] - s * p; s++; } next[s2] = low < INF ? low + (s2 + d) * p + fare + s2 * keep : INF; if (s2 + d <= cap && best[s2 + d] < INF && best[s2 + d] + s2 * keep < next[s2]) { next[s2] = best[s2 + d] + s2 * keep; /* 가게에 가지 않는 날: 차비가 없다 */ } } memcpy(best, next, sizeof(long long) * (cap + 1)); } /* 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다 */ printf("%lld\n", best[0]); return 0;}
Craykonmain.cray · 45 行
첫줄 = コンソール.数読み();n = 첫줄[0];cap = 첫줄[1];keep = 첫줄[2];fare = 첫줄[3];price = コンソール.数読み();eat = コンソール.数読み();// best[s] = 지난밤 냉장고에 s개를 넣어 둔 채 오늘을 맞을 때까지 든 가장 적은 돈(-1은 아직 그렇게 될 수 없음)best = 新リスト(cap + 1, -1);best[0] = 0;繰り返す (day = 0; day < n; day++){ p = price[day]; d = eat[day]; // 오늘 아침 s개, 오늘 b개를 사서 d개를 먹고 밤에 s2개를 남기면 b = s2 + d - s // 가게에 가지 않으면 b = 0이라 s = s2 + d 하나뿐이다: best[s2 + d] + s2 * keep // 가게에 가면 돈 = (best[s] - s * p) + (s2 + d) * p + fare + s2 * keep (s <= s2 + d): 앞 괄호의 최솟값만 알면 된다 next = 新リスト(cap + 1, -1); low = なし; // s = 0 .. min(cap, s2 + d) 가운데 best[s] - s * p의 최솟값(빈값은 아직 없음) s = 0; 繰り返す (s2 = 0; s2 <= cap; s2++) { 間 (s <= cap && s <= s2 + d) { もし (best[s] != -1 && (low == なし || best[s] - s * p < low)) { low = best[s] - s * p; } s++; } もし (low != なし) { next[s2] = low + (s2 + d) * p + fare + s2 * keep; } // 가게에 가지 않는 날: 차비가 없다 もし (s2 + d <= cap && best[s2 + d] != -1 && (next[s2] == -1 || best[s2 + d] + s2 * keep < next[s2])) { next[s2] = best[s2 + d] + s2 * keep; } } best = next;}// 마지막 날 밤에 남기는 과자는 돈만 더 드니 0개 남기는 것이 가장 싸다コンソール.書く(best[0]);