题目名称	2470. [EZOI 2016]D.VA翻转硬币
输入输出	`zhrmghg.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	Ezoi_Vermouth 于2016-09-21加入
开放分组	全部用户
提交状态
分类标签	贪心 EZOI
	分享题解

通过：6，提交：8，通过率：75%
沉迷学习的假的Keller	100	0.000 s	0.00 MiB	C++
Ezoi_强势占领	100	0.000 s	0.00 MiB	C++
Hakurou!	100	0.000 s	0.00 MiB	C++
Magic_Sheep	100	0.000 s	0.00 MiB	C++
Ezoi_Vermouth	100	0.037 s	2.58 MiB	C++
svideo	100	0.054 s	2.58 MiB	C++
ha sa ki	0	0.018 s	0.31 MiB	C++
Hakurou!	0	10.012 s	11.93 MiB	C++

关于 D.VA翻转硬币的近10条评论(全部评论)
可以，很强势新的overwatch:Ezoi Janis 2016-09-22 21:12 6楼
听说很强势 ha sa ki 2016-09-22 20:01 5楼
`#include <cstdio> int main() { while(1)printf("Orz LPX"); return 0; }` Hakurou! 2016-09-22 14:01 4楼
Ezoi 已经占领此题 Orz...LPX svideo 2016-09-22 13:50 3楼
Ezoi 强势占领系列 Ezoi_强势占领 2016-09-22 13:50 2楼
%%% AntiLeaf 2016-09-22 13:46 1楼

2470. [EZOI 2016]D.VA翻转硬币

★★★ 输入文件：zhrmghg.in 输出文件：zhrmghg.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

一共有n 个硬币，D.VA每次会翻转k 个硬币。每次翻转k 个硬币，他的兴奋度会增加p，但同时兴奋度会减去被翻转硬币的生锈度。也就是说比如当前硬币的正面生锈度为2，那么他把这枚硬币翻转到反面，兴奋度会增加p，同时兴奋度又减少了2。注意，翻硬币也是会疲倦的，每一次翻转后p 会减少1。所以你不能让D.VA无休止地把硬币翻下去。一开始硬币的正反面情况为$a_1,a_2,a_3,.....,a_n$。D.VA 的目标是把这些硬币都翻到与开始时相反的一面。1 表示正面，0 表示反面。于是battle作为一个“关心学生”的好老师，他请你找出一个最好的硬币翻转方案，使得D.VA 的兴奋度增加值最大.

【输入格式】

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

第二行：n 个数：$a_1,a_2,a_3,......,a_n$。表示硬币的初始状态。

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

【输出格式】

第一行：D.VA 在达到目标的前提下最大的兴奋度。如果D.VA 无法兴奋，

即无解或兴奋度小于0，则输出0 表示不可能。

【样例输入】

5 3 22

1 1 1 1 1

5 6

6 7

7 8

5 7

6 8

【样例输出】

【提示】

对于50%的数据：$0<k<=n<=15；0<=a_i,p<20$.

对于80%的数据：$0<k<=n<=20；0<=a_i,p<20$.

对于100%的数据：$0<k<=n<=100000；0<=a_i,p<1000000$.

【来源】

未知，请尊重原创题目作者，本题非本人原创.