#P1. [Sleeping Cup #1] Sleeping pairs
[Sleeping Cup #1] Sleeping pairs
注意
本题需要使用文件读写(pairs.in
/ pairs.out
)。
题目背景
小 C 是一间卧铺车厢的管理员。这间车厢内有若干张床,每张床都分上下铺(即每张床可以睡 个人)。这天,正当它满载着乘客行驶时,车厢里突然停电了!
这立刻激起了乘客们的愤怒。他们要求小 C 妥善处理这个问题,把他们转移到另一间车厢。同时,有些人借此向小 C 抱怨,他们的上铺(或下铺)睡觉时打呼噜,使得他们无法入睡。
题目描述
小 C 向你总结了他所需要解决的问题:
- 车厢内共有 张床,每张床都分上下铺,相当于一张 行 列的表格。
- 每张床位上都有一位乘客。有的乘客会打呼噜(用
Z
表示),有的乘客不会(用X
表示)。也就是说,每个格子中都有一个字符Z
或X
。 - 乘客们希望同一张床中上下铺乘客的属性(即是否打呼噜)相同,即要求每行 个格子中的字符相同。
- 小 C 可以做以下操作,每操作一次(每次只能选择下面一项进行操作)花费 点体力:
- 交换两个相邻的乘客(相邻两床的上铺,相邻两床的下铺,或者同一床的上下铺),即交换 个相邻格子中的字符。
- 移走一张上下铺安排符合乘客预期的床,即删除表格中符合要求的一行。
- 现要求移走所有的床(即删空表格,保证可以实现),问最少需要多少点体力。
输入格式
第一行一个正整数 。
下面 行,每行 个字符,形成一个 行 列的表格。
输出格式
一行一个正整数,表示答案。
样例
3
XZ
ZZ
ZX
4
18
XX
XX
XX
XX
XZ
ZX
XZ
ZZ
XZ
XZ
ZZ
XZ
ZX
XZ
XX
XX
XX
XX
24
提示
样例 解释:
一种最优的操作方案是:删除第 行,交换第 列(或第 列)剩下的的 个字符,再分别删除剩下的 行,一共花费 点体力。
对于 的数据,,且 X
和 Z
均有偶数个(保证可以达成目标)。
相关
在下列比赛中: