问题描述：
要求求一个点(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]，于是问题就解决了，每次统计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);
}
}