分数: 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 可以通过执行如下操作来获得,并且这是最小值。
示例输入 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