← 返回题单
题单练习 动态规划的优化
← 上一题 下一题 →

A7073 | fangz 补习班

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

在补习班上，因为多个学生会同时有提问需求，所以 fangz 会制造分身，用音速在教室里来回回答问题。

补习班上有 $n$ 个同学，他们每一个人都有一个问题。fangz 为了有序回答学生的问题，把所有学生排成了一列。第 $i$ 个学生的问题有一个困难值 $a_i$，fangz 回答第 $i$ 个学生的问题需要花费 $a_i$ 点精力。fangz 到了哪一个学生那里，就必须解决那名学生的问题。

  • fangz 最开始会解决序列中第 $1$ 个同学的问题；
  • fangz 最后会去解决第 $n$ 个同学的问题；
  • 期间 fangz 一直向编号增大的方向移动，不能后退。

    • 当 fangz 解决完当前编号为 $p$ 的学生后，准备去下一位学生那里，如果只是走到编号为 $p+1$ 的下一个学生，则需要花费 $k$ 点精力值。

    特殊地，如果 fangz 想让自己轻松一点，可以不去下一个，而是直接去下两个、下三个……也就是从位置 $p$ 直接跳到位置 $q$（$qp$）而不解决中间同学的问题。但是，被跳过的学生会在一旁疯狂吐槽，给 fangz 的心灵造成打击，于是这一跳总共要花费的精力变为
    $$ k + (q-p-1)\times d, $$
    其中 $q-p-1$ 是被跳过的学生人数。

    注意：当 $q = p+1$ 时，$q-p-1=0$，这一跳的精力消耗仍然是 $k$。也就是说，上面这个公式对所有合法的 $qp$ 都适用。


    当然，fangz 也想尽量解决一些同学的问题，所以他规定每次最多只能连续跳过 $x-1$ 个学生，也就是说，从位置 $p$ 最远只能跳到 $p+x$（如果不超过 $n$）。形式化地，每一步移动中，$q$ 需要满足
    $$ p+1 \le q \le \min(p+x,\,n). $$

    总结一下：你需要安排一条从 $1$ 号学生到 $n$ 号学生的访问路线
    $$ 1 = i_1 i_2 \dots i_m = n, $$
    每次从 $i_t$ 跳到 $i_{t+1}$，满足 $1 \le i_{t+1}-i_t \le x$，并且：
  • 每访问到一名学生 $i_t$，就要额外花费 $a_{i_t}$ 点精力；
  • 从 $i_t$ 跳到 $i_{t+1}$ 的移动精力为
$$ k + (i_{t+1}-i_t-1)\times d. $$

请你计算，fangz 为了从第 $1$ 个学生走到第 $n$ 个学生，解决完他所到之处所有学生的问题，最少需要花费多少精力。

输入格式

第一行包含四个整数 $n,k,d,x$，表示：

  • $n$：学生的总数量；
  • $k$：每次向后移动到某个学生的基础精力消耗；
  • $d$：每多跳过一个学生需要额外增加的精力；
  • $x$：每一步最多可以跳过 $x-1$ 个学生（即每步最远可以从 $p$ 跳到 $p+x$）。
第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，其中 $a_i$ 表示第 $i$ 个学生的问题的困难值。

输出格式

输出一行一个整数，表示 fangz 解决完第 $n$ 个同学的问题，最少需要花费多少精力。

输入输出样例

输入 #1
5 3 4 1
1 2 3 4 5
输出 #1
27
C++ 编辑器
输入
输出