bzoj#P1953. [2009 国家集训队] 神奇的 K 线

[2009 国家集训队] 神奇的 K 线

题面不完整。

题目描述

小明爱上了炒股。经过近段时间的观察和整理,他发现了如果一个股票出现了某种形态的 K 线,那么这个股票不久之后一定会大涨。小明想利用这种神奇的 K 线来做一个股票软件。他将一条 K 线用整数序列 aa 来表示,并规定当且仅当 ai+1ai=pia_{i+1} - a_{i} = p_{i} 时,这条 K 线是一条神奇的 K 线。但是事情总不是一帆风顺的,小明发现许多 K 线不是神奇的,但之后也能大涨。不过他发现这些 K 线都和神奇的 K 线很接近。为了进一步扩展神奇的 K 线的用途,小明定义了两条 K 线 bbaa 的差异度:

bb 中某一个元素修改成任意值的代价为 cost1cost_1,将 bb 中某一个元素删除的代价为 cost2cost_2。将 bb 修改成 aa 的前缀的最小的代价和就是 bbaa 的差异度。

这里的前缀的定义有点特别,假设 bb 的长度为 mmbbaa 的前缀当且仅当 bi+1bi=ai+1aib_{i+1}-b_{i}=a_{i+1}-a_{i}1i1 \leq i

输入格式

第一行三个正整数 n,cost1,cost2n, cost_1, cost_2nn 表示给出的 K 线 aa 的长度,cost1cost_1cost2cost_2 的含义如题。

第二行 n1n-1 个整数,依次表示 p1p_1pn1p_{n-1},含义如题。

第三行 nn 个整数,依次表示给出的 K 线 aa 中的 nn 个元素。

输出格式

一个数,aa 和神奇的 K 线的差异度。

8 1 2
1 2 3 4 5 6 7
0 1 999 6 10 -999 15 21
3

样例解释 1

999999 改为 33,删去 999-999,得到序列 0,1,3,6,10,15,210,1,3,6,10,15,21。不存在代价更小的方案。

数据规模与约定

对于 100%100\% 的数据,n1.5×103n \leq 1.5 \times 10^3cost1,cost2106cost_1, cost_2 \leq 10^6pi103\forall \left| p_i \right| \leq 10^3ai106\forall \left| a_i \right| \leq 10^6

题目来源

By 李宇亮