HBC19949[CQOI2017]老C的方块题解

想要成为编程高手？那就来试试全网最全C++题库，让您在练习中快速成长。

老 C 懒得思考,就把这个问题交给你了

老 C 是个程序员。      作为一个懒惰的程序员,老 C 经常在电脑上玩方块游戏消磨时间。游戏被限定在一个由小方格排成的R行C列网格上 ,如果两个小方格有公共的边,就称它们是相邻的,而且有些相邻的小方格之间的公共边比较特殊。特殊的公共边排 列得有很强的规律。首先规定,第1行的前两个小方格之间的边是特殊边。然后,特殊边在水平方向上每4个小方格为 一个周期,在竖直方向上每2个小方格为一个周期。所有的奇数列与下一列之间都有特殊边,且所在行的编号从左到 右奇偶交替。下图所示是一个R = C = 8的网格,蓝色标注的边是特殊边。首先,在第1行,第1列和第2列之间有一条 特殊边。因为竖直方向周期为2,所以所有的奇数行,第1列和第2列之间都有特殊边。因为水平方向周期为4,所以所 有奇数行的第5列和第6列之间也有特殊边,如果网格足够大,所有奇数行的第9列和第10列、第13列和第14列之间都 有特殊边。因为所有的奇数列和下一列之间都有特殊边,所以第3列和第4列、第7列和第8列之间也有特殊边,而所在 行的编号从左到右奇偶交替,所以它们的特殊边在偶数行。如果网格的规模更大,我们可以用同样的方法找出所有的特殊边。 网格的每个小方格刚好可以放入一个小方块,在游戏的一开始,有些小方格已经放上了小方块,另外的小方格没有放 。老 C 很讨厌下图所示的图形,如果他发现有一些小方块排列成了它讨厌的形状(特殊边的位置也要如图中所示), 就很容易弃疗,即使是经过任意次旋转、翻转后排列成讨厌的形状,老 C 也同样容易弃疗。 为了防止弃疗,老 C 决定趁自己还没有弃疗,赶紧移除一些格子里小方块,使得剩下的小方块不能构成它讨厌的形状 。但是游戏里每移除一个方块都是要花费一些金币的,每个方块需要花费的金币有多有少参差不齐。老 C 当然希望 尽可能少的使用游戏里的金币,但是最少要花费多少金币呢?老 C 懒得思考,就把这个问题交给你了

标签： HBC19949[CQOI2017]老C的方块题解