#P3480. [Usaco2014 Mar]Mooo

    ID: 2692 传统题 1000ms 512MiB 尝试: 158 已通过: 82 难度: 3 上传者: 标签>难度分类普及构造与建模差分转化动态规划完全背包CF1300Silver

[Usaco2014 Mar]Mooo

Mooo Moo

题目描述

农夫约翰忘了自己有多少头奶牛,决定在各块田里放置麦克风,利用听到的叫声大小计算奶牛数量。

NN 块田从左到右排成一列。约翰的奶牛来自 BB 个品种,品种 ii 的一头奶牛发出的叫声音量为 ViV_i。每块田可以有多头、多个品种的奶牛,也可以没有奶牛。

风把叫声从左向右传递。如果一块田记录到的总音量为 XX,它会为右边紧邻的田贡献 max⁡(0,X−1)\max(0,X-1) 的音量。每块田记录到的音量等于本田所有奶牛的叫声音量之和,加上左边紧邻田传来的音量。最左边的田没有来自其他田的音量。

根据各块田的记录,求与记录相符的最少奶牛数。

输入格式

第一行包含两个整数 N,BN,B。

接下来 BB 行,第 ii 行包含品种 ii 的叫声音量 ViV_i。

再接下来 NN 行,从左到右给出各块田记录的总音量。

输出格式

输出一个整数,表示约翰可能拥有的最少奶牛数。如果无法得到给定的记录,输出 −1-1。

样例 #1

5 2
5
7
0
17
16
20
19
4

第 22 块田有两头品种 11 的奶牛和一头品种 22 的奶牛,第 44 块田有一头品种 11 的奶牛。

数据范围

1≤N≤1001\le N\le 100,1≤B≤201\le B\le 20,1≤Vi≤1001\le V_i\le 100。各块田记录的总音量为 00 到 10510^5 之间的整数。