n 天里每天都吃零食。
第 i 天必须正好吃 dᵢ 个零食，那天商店以每个 pᵢ 元的价格想买多少就卖多少。
买零食的那天要去一趟商店，不管买多少个，当天都要付一次车费 f 元。
一个零食也不买的那天不去商店，所以没有车费。
零食可以当天吃，也可以放进冰箱留到之后的某天再吃。
每天按买、吃、放进冰箱的顺序度过。
当天吃完剩下的零食必须在当晚全部放进冰箱，冰箱最多放 C 个。
放在冰箱里的零食每晚每个要付 h 元保管费。
第一天早上一个零食也没有。
最后一天晚上如果还剩零食，也要放进冰箱并付保管费。
输出在 n 天里按规定数量吃完所需花费（零食钱、车费与保管费之和）的最小值。
4 3 1 8 2 9 9 3 2 2 2 1
49
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
状态是“当晚留在冰箱里的个数 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 == 空 || …）。
import sys data = 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])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]);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]);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]); }}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]); }}#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;}#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;}첫줄 = 控制台.读数字();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]);