Monge矩陣
對一個m*n的實數矩陣A，如果對所有i，j，k和l，1≤ i<k ≤ m和1≤ j<l ≤ n，有 ? ? ? ? ?A[i,j]+A[k,l] ≤ A[i,l]+A[k,j] ? 那么，此矩陣A為Monge矩陣。
換句話說，每當我們從矩陣中挑出兩行與兩列，并且考慮行列交叉處的4個元素，左上角與右下角的和小于或等于左下角與右上角元素的和。
例如，下面這個就是一個Monge矩陣
（1）證明一個矩陣為Monge陣，當且僅當對所有i=1,2,...,m-1和j=1,2,...,n-1，有 ? ? ? ? ? ?A[i,j]+A[i+1,j+1] ≤ A[i,j+1]+A[i+1,j]
(提示:在當部分，對行、列分別使用歸納法。)
（2）下面的矩陣不是Monge陣。改變一個元素，把它變成Monge矩陣
???????????? 37?????? 23?????? 22????? 32
???????????? 21??????? 6?????? 27????? 10
???????????? 53?????? 34?????? 30????? 31
???????????? 32?????? 13??????? 9?????? 6
???????????? 43?????? 21?????? 15?????? 8
很明顯是要改27,27可以改成【2,5】內的任何一個實數
（3）假設f(i)是第i行包含最左端最小值的列的索引值。證明對任何的m x n Monge矩陣，有f(1) ≤ f(2) ≤...≤ f(m)。
（4）下面是一個用來計算m x n 的Monge矩陣A中每一行的最左最小值的分治算法的描述：
?? 構造一個包含所有A的偶數行的子矩陣A'。遞歸地計算A'中每一行的最左端最小值。然后計算A中奇數行的最左端最小值。
?? 解釋如何能在O(m+n)時間內計算出A的奇數行的最左端最小值？（在偶數行最左最小值已知的情況下）
解釋：看下面的代碼就很明顯了。
其實這個算法，我個人感覺，就結構而言比較像分治，但是就思想而言比較像動態規劃。
（5）寫出（4）所描述算法的運行時間的遞歸式，并證明其解為O(m+nlogm)
T（m）=T（m/2）+ O（m+n）（求解略）
我的代碼：
?
#include<iostream>
using namespace std;void calculate(double **A, int r1, int r2, int min, int max, int *f) //計算f(r1)到f(r2)
{if (r1 > r2)return;int r = (r1 + r2) / 2;int result = min;int flag = A[r][min];for (int i = min + 1; i <= max; i++) //尋找最左最小元素flag，和它的的下標result{if (A[r][i] < flag){flag = A[r][i];result = i;}}f[r] = result;calculate(A, r1, r - 1, min, result, f);calculate(A, r + 1, r2, result, max, f);
}bool isMonge(double **A, int m, int n) //判斷是否是Monge矩陣
{for (int i = 0; i < m - 1; i++)for (int j = 0; j < n - 1; j++)if (A[i][j] + A[i + 1][j + 1]>A[i + 1][j] + A[i][j + 1])return false;return true;
}
int main()
{int m, n;while (cin >> m >> n && m>1 && n > 1){double **A = new double*[m]; //Monge矩陣int *f = new int[m]; //不需要在主函數里面進行初始化，這個工作由calculate函數完成for (int i = 0; i < m; i++){A[i] = new double[n];for (int j = 0; j < n; j++)cin >> A[i][j];}if (isMonge(A, m, n)){cout << "這個是Monge矩陣" << endl;calculate(A, 0, m - 1, 0, n - 1, f);for (int i = 0; i < m; i++)cout << "第" << i << "行的最左最小元素的列下標是" << f[i] << endl;}else cout << "這個不是Monge矩陣";}return 0;
}
)
