P2844 LJJ翻硬币

    • 2通过
    • 29提交
  • 题目提供者 eden
  • 评测方式 云端评测
  • 标签 搜索 数论,数学 模拟 贪心
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    LJJ在考试的时候由于不会选择题、填空题、解答题,于是,他通过抛硬币来决定写什么(填空、解答题里的每一个字符都通过抛硬币决定,强到不行,竟然满分,于是LJJ贡他唯一的硬币为神灵)。但是抛着抛着,LJJ发现翻硬币的游戏非常好玩,竟然比扫雷还好玩!于是,为了增加他的兴奋度,他就会进行一个游戏——从同学那里借来硬币摆成一行(毕竟他只有一个),并且兴(wu)奋(liao)地翻转其中的某些硬币。

    但由于是同学借给他的,所以都是生锈的(为同学点赞),数据会给出每个硬币正面和反面的生锈度。

    一共有n个硬币,LJJ每次会翻转k个硬币。每次翻转k个硬币,他的兴奋度会增加p,但同时兴奋度会减去每个被翻转硬币的生锈度之和。也就是说比如他准备翻2个正面向上的硬币,当前硬币的正面生锈度分别为2、3,那么他把这两枚硬币翻转到反面,兴奋度会增加p,同时兴奋度又减少了5。

    注意,翻硬币也是会疲倦的,每一次翻转后p会减少1。所以你不能让LJJ无休止地把硬币翻下去。

    一开始硬币的正反面情况为a1,a2,a3,.....,an。LJJ的目标是把这些硬币都翻到与开始时相反的一面。1表示正面,0表示反面。

    于是PJY作为一个“关心学生”的好老师,他请你找出一个最好的硬币翻转方案,使得LJJ…

    输入输出格式

    输入格式:

    第一行:n,k,p三个正整数。详见描述。

    第二行:n个数:a1,a2,a3,......,an。表示硬币的初始状态。

    第三行到第(2+n)行:每行两个数x,y,表示第i个硬币正面和反面的生锈度。

    输出格式:

    第一行:LJJ在达到目标的前提下最大的兴奋度。如果LJJ无法兴奋,即无解或兴奋度小于0,则输出0表示不可能。

    输入输出样例

    输入样例#1: 复制
    5  3  22
    1 1 1 1 1
    5 6
    6 7
    7 8
    5 7
    6 8
    输出样例#1: 复制
    12

    说明

    对于50%的数据:0<k<=n<=15。(送分)

    对于80%的数据:0<k<=n<=20;0<=ai,p<20。(正常)

    对于100%的数据:0<k<=n<=100000;0<=ai,p<1000000。(这是个坑)

    样例说明:

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