問題描述：
要求求一個點(r, c)使得它到達(i, j)的曼哈頓距離與該點權值乘積總和最小，其中(1 <= i <= n, 1 <= j <= m)
(1 <= n, m <= 100) 因此，暴力的復雜度是O(n^4)，顯然是TLE的，想了一下，想到一個O(n^3)的算法，算法核心還是DP。
解題思路：
首先定義:
map[i][j] 表示原圖(i, j)這個點的權值
sum[i][j] 表示第1行一直到第i行中所有第j列的權值總和
rt[i][j] 表示以該點為(r, c)而得到的權值總和
答案就是 Min = min{rt[i][j] , (1 <= i <= n, 1 <= j <= m) }
首先預處理sum[i][j] ，然后每次暴力計算rt[i][1]的值，由于rt[i][j-1] 和rt[i][j]相鄰，于是他們相對于別的點曼哈頓距離必定均相差1，每次計算rt[i][j]只要枚舉列k，如果第k列在j-1以及其左邊那么rt[i][j] 比rt[i][j-1]大sum[n][k]，否則要小sum[n][k]，于是問題就解決了，每次統(tǒng)計rt[i][j]然后取最小值即可。
核心代碼：
if(k <= j-1)
rt[i][j] += sum[n][k];
else
rt[i][j] -= sum[n][k];
#include <iostream>
using namespace std;
int n, m, i, j, k;
int Min;
int map[101][101];
int sum[101][101];
int rt[101][101];
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
Min = -1;
scanf("%d %d", &m, &n);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
scanf("%d", &map[i][j]);
}
}
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
sum[i][j] = sum[i-1][j] + map[i][j];
}
for(i = 1; i <= n; i++)
{
rt[i][1] = 0;
//計算(i, 1) 這個點作為Ketichen的距離和
for(j = 1; j <= n; j++)
{
for(k = 1; k <= m; k++)
{
rt[i][1] += ( abs(i-j) + abs(k-1) ) * map[j][k];
}
}
if(Min == -1 || rt[i][1] < Min)
Min = rt[i][1];
//根據(i, j-1)計算(i, j)的值
for(j = 2; j <= m; j++)
{
rt[i][j] = rt[i][j-1];
for(k = 1; k <= m; k++)
{
if(k <= j-1)
rt[i][j] += sum[n][k];
else
rt[i][j] -= sum[n][k];
}
if(Min == -1 || rt[i][j] < Min)
Min = rt[i][j];
}
}
printf("%d blocks\n", Min);
}
}