P3943 星空

    • 167通过
    • 1.5K提交
  • 题目提供者 fstqwq 管理员
  • 评测方式 云端评测
  • 标签 差分 状态压缩,状压 背包 O2优化
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    pdf题面和大样例链接:http://pan.baidu.com/s/1cawM7c 密码:xgxv

    命运偷走如果只留下结果, 时间偷走初衷只留下了苦衷。
    你来过,然后你走后,只留下星空。

    题目描述

    逃不掉的那一天还是来了,小 F 看着夜空发呆。

    天上空荡荡的,没有一颗星星——大概是因为天上吹不散的乌云吧。

    心里吹不散的乌云,就让它在那里吧,反正也没有机会去改变什么了。

    小 C 拿来了一长串星型小灯泡,假装是星星,递给小 F,想让小 F 开心一点。不过,有 着强迫症的小 F 发现,这串一共 n 个灯泡的灯泡串上有 k 个灯泡没有被点亮。小 F 决定 和小 C 一起把这个灯泡串全部点亮。

    不过,也许是因为过于笨拙,小 F 只能将其中连续一段的灯泡状态给翻转——点亮暗灯 泡,熄灭亮灯泡。经过摸索,小 F 发现他一共能够翻转 m 种长度的灯泡段中灯泡的状态。

    小 C 和小 F 最终花了很长很长很长很长很长很长的时间把所有灯泡给全部点亮了。他 们想知道他们是不是蠢了,因此他们找到了你,让你帮忙算算:在最优的情况下,至少需要 几次操作才能把整个灯泡串给点亮?

    输入输出格式

    输入格式:

    从标准输入中读入数据。

    输入第 1 行三个正整数 n,k,m。

    输入第 2 行 $k$ 个正整数,第 i 个数表示第 i 个被没点亮的灯泡的位置 $a_i$ 。

    输入第 3 行 $m$ 个正整数,第 i 个数表示第 i 种操作的长度 $b_i$ 。

    保证所有 $b_i$ 互不相同;保证对于 $1 \le i < k$ ,有 $a_i< a_i+1$ ;保证输入数据有解。

    输出格式:

    输出标准输入中。

    输出一行一个非负整数,表示最少操作次数。

    输入输出样例

    输入样例#1: 复制
    5 2 2 
    1 5 
    3 4
    输出样例#1: 复制
    2   
    

    说明

    【样例 1 解释】

    【数据范围与约定】

    子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难,可以尝试只解 决一部分测试数据。

    每个测试点的数据规模及特点如下表

    特殊性质:保证答案小于 4

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。