YZOJ P2417 [FJWC2016][CF79-D]翻转硬币
时间限制:1000MS 内存限制:131072KB
难度: \(6.0\)
-
题目描述
\(n\) 枚硬币正面朝上摆成一排,给定 \(a_1, a_2, \cdots, a_m\),每次操作可以任意选择一个 \(a_i\),并翻转连续 \(a_i\) 个硬币。
要求经过最少次数的操作,使得仅第 \(x_1, x_2, \cdots, x_k\) 枚硬币反面朝上,输出最少次数。
-
输入格式
第一行三个整数 \(n\)、\(k\)、\(m\) 。
第二行 \(k\) 个整数表示需要反面朝上的硬币位置,从 \(1\) 编号。
第三行 \(m\) 个整数表示 \(a_1, a_2, \cdots, a_m\) 。
-
输出格式
一个整数表示答案,若无解,则输出 \(-1\) 。
-
样例输入
1 2 3 |
10 8 2 1 2 3 5 6 7 8 9 3 5 |
-
样例输出
1 |
2 |
-
数据规模与约定
对于 \(30\%\) 的数据,\(n, m \leq 10\) 。
对于 \(60\%\) 的数据,\(m \leq 20\) 。
对于 \(100\%\) 的数据,\(1 \leq n \leq 10000\),\(1 \leq k \leq 10\),\(1 \leq m \leq 100\),\(1 \leq a_i \leq n\) 。
Source: CF79-D…