P1251 Napkin Planning Problem

A restaurant needs different numbers of napkins on $N$ consecutive days. Suppose on day $i$ it needs $r_i$ napkins ($i = 1, 2, \dots, N$). The restaurant can buy new napkins at a cost of $p$ cents per napkin; or send used napkins to a fast laundry, which takes $m$ days and costs $f$ cents per napkin; or send them to a slow laundry, which takes $n$ days ($n \gt m$) and costs $s$ cents per napkin ($s \lt f$). At the end of each day, the restaurant must decide how many dirty napkins to send to the fast laundry, how many to send to the slow laundry, and how many to store for later laundering. On each day, the total number of napkins returned from laundries that day plus newly purchased napkins must meet that day’s demand. Design an algorithm to plan napkin usage over $N$ days so that the total cost is minimized. Write a program to find an optimal napkin usage plan.

Input is given via standard input. The first line contains one positive integer $N$, the number of days to plan. The next line contains the restaurant’s napkin demand for each of the $N$ consecutive days. The last line contains $5$ positive integers $p, m, f, n, s$. Here, $p$ is the cost per new napkin; $m$ is the number of days the fast laundry takes per napkin; $f$ is the cost per napkin at the fast laundry; $n$ is the number of days the slow laundry takes per napkin; $s$ is the cost per napkin at the slow laundry.

Output the minimum total cost of napkin usage over the $N$ consecutive days.

Constraints: For $100\%$ of the testdata, $1 \le N \le 2 \times 10^3$, $1 \le r_i \le 10^7$, $1 \le p, f, s \le 10^4$. Translated by ChatGPT 5