餐巾计划问题

题目来源

网络流 24 题

题目描述

一个餐厅在相继的 $n$ 天里，每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾。

每天餐厅可以如下操作：

• 购买新的餐巾,每块餐巾的费用为 $c_0$。
• 把旧餐巾送到快洗部，洗一块需 $d_1$ 天，费用为 $c_1$。
• 把旧餐巾送到慢洗部，洗一块需 $d_2$ 天，费用为 $c_2$。

每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $n$ 天中餐巾使用计划，使总的花费最小。

输入格式

第一行六个正整数 $n, c_0, d_1, c_1, d_2, c_2 (1\leq n \leq 800, 1\leq c_i\leq 100)$。

接下来 $n$ 行每行包含一个整数 $r_1, r_2, \dots, r_n (1\leq r_i\leq 1000)$。

输出格式

将餐厅在相继的 $n$ 天里使用餐巾的最小总花费输出。

样例输入

3 11 2 2 3 1
1
7
5

样例输出

134