← 返回题目列表

AtCoder · codefestival_2016_qualC_d

D. 摩擦力

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

高桥先生的房间里有一件艺术品 H 行和 W 列,由 H \times W 块。 每个块都有一个由小写英文字母表示的颜色(a-z)。 块的颜色 i第行和 j第列是 c_{i,j}.

高桥先生想拆解这个物体,因为他发现它对他的口味来说有点俗气。 拆解是通过重复以下操作进行的:

  • 选择其中一项 W 列并将该列下推一行。 该列底部的方块消失。

每次执行操作时,都会开始消耗。 由于相同颜色的块具有相互绘制在一起的属性,因此操作的成本是块对的数量 (p, q) 这样:

  • 块 p 位于所选列中。
  • 两个区块 p 和 q 水平相邻(在向下推列之前)。
  • 两个区块 p 和 q 具有相同的颜色。

高桥先生通过重复操作将物体拆除 H \times W 次消除所有方块。 计算拆除该物体的最小总成本。

约束

  • 1 ≤ H ≤ 300
  • 2 ≤ W ≤ 300
  • 所有字符 c_{i,j} 为小写英文字母 (a-z).

部分分数

  • 在测试用例中值得 300 点, W = 3.

输入

输入由标准输入按以下格式给出:

H W
c_{1,1}c_{1,2}..c_{1,W}
c_{2,1}c_{2,2}..c_{2,W}
:
c_{H,1}c_{H,2}..c_{H,W}

输出

打印拆除该物体的最小总成本。


示例输入 1

2 3
rrr
brg

示例输出 1

2

例如,总成本 2 可以通过执行如下操作来获得,并且这是最小值。

ccb25ed6f1df9367829b68523e1deff4.png

示例输入 2

6 3
xya
xya
ayz
ayz
xaz
xaz

示例输出 2

0

总成本 0 可以通过首先按下中间列的所有块,然后按下所有左列和所有右列来实现。


示例输入 3

4 2
ay
xa
xy
ay

示例输出 3

0

总成本 0 可以通过以下操作实现:

  • 右列下推一行;
  • 左栏下推一行;
  • 按下所有右栏;
  • 并按下所有左栏。 如果

示例输入 4

5 5
aaaaa
abbba
ababa
abbba
aaaaa

示例输出 4

24

示例输入 5

7 10
xxxxxxxxxx
ccccxxffff
cxxcxxfxxx
cxxxxxffff
cxxcxxfxxx
ccccxxfxxx
xxxxxxxxxx

示例输出 5

130