#P1311. 最优压缩

    ID: 323 传统题 1000ms 512MiB 尝试: 76 已通过: 37 难度: 6 上传者: 标签>CF2000提高最小割建模最大流最小割定理Dinic当前弧优化残量网络

最优压缩

题目描述

灰度图像由 N×MN\times M 的整数矩阵 AA 表示,灰度取值为 00 到 255255。选定两个参考灰度 V0,V1V_0,V_1 后,需把每个像素改为其中之一。令 Wij∈{0,1}W_{ij}\in\{0,1\},修改后的灰度为 VWijV_{W_{ij}}。

修改方案的估价值定义为

$$E=\sum_{i,j}|A_{ij}-V_{W_{ij}}|+ \sum_{\{(i,j),(u,v)\}\in\mathcal E}|W_{ij}-W_{uv}|\,|A_{ij}-A_{uv}|,$$

其中 E\mathcal E 为所有上下或左右相邻的像素对,每个无序像素对只计一次。第一项衡量单个像素的修改代价,第二项对相邻像素选择不同参考灰度的情况计费。求最小估价值。

输入格式

第一行两个整数 N,MN,M,1≤N,M≤351\le N,M\le35。第二行两个整数 V0,V1V_0,V_1,接下来 NN 行每行 MM 个整数,为矩阵 AA。所有灰度均在 [0,255][0,255] 内。

输出格式

输出一个整数,表示最小估价值。

样例输入

1 2
0 255
10 20

样例输出

30