#P1311. 最优压缩
最优压缩
题目描述
灰度图像由 的整数矩阵 表示,灰度取值为 到 。选定两个参考灰度 后,需把每个像素改为其中之一。令 ,修改后的灰度为 。
修改方案的估价值定义为
$$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}|,$$其中 为所有上下或左右相邻的像素对,每个无序像素对只计一次。第一项衡量单个像素的修改代价,第二项对相邻像素选择不同参考灰度的情况计费。求最小估价值。
输入格式
第一行两个整数 ,。第二行两个整数 ,接下来 行每行 个整数,为矩阵 。所有灰度均在 内。
输出格式
输出一个整数,表示最小估价值。
样例输入
1 2
0 255
10 20
样例输出
30