英雄哪里出來

問題描述：
要求求一個點(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);
    }
}