YZOJ P2417 [FJWC2016][CF79-D]翻转硬币

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\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(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