英雄哪里出來(lái)

問(wèn)題描述：
要求求一個(gè)點(diǎn)(r, c)使得它到達(dá)(i, j)的曼哈頓距離與該點(diǎn)權(quán)值乘積總和最小，其中(1 <= i <= n, 1 <= j <= m)
(1 <= n, m <= 100) 因此，暴力的復(fù)雜度是O(n^4)，顯然是TLE的，想了一下，想到一個(gè)O(n^3)的算法，算法核心還是DP。
解題思路：
首先定義:
map[i][j]       表示原圖(i, j)這個(gè)點(diǎn)的權(quán)值
sum[i][j]       表示第1行一直到第i行中所有第j列的權(quán)值總和
rt[i][j]           表示以該點(diǎn)為(r, c)而得到的權(quán)值總和
答案就是 Min = min{rt[i][j] , (1 <= i <= n, 1 <= j <= m) }

首先預(yù)處理sum[i][j] ，然后每次暴力計(jì)算rt[i][1]的值，由于rt[i][j-1] 和rt[i][j]相鄰，于是他們相對(duì)于別的點(diǎn)曼哈頓距離必定均相差1，每次計(jì)算rt[i][j]只要枚舉列k，如果第k列在j-1以及其左邊那么rt[i][j] 比rt[i][j-1]大sum[n][k]，否則要小sum[n][k]，于是問(wèn)題就解決了，每次統(tǒng)計(jì)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;

            //計(jì)算(i, 1) 這個(gè)點(diǎn)作為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];

            //根據(jù)(i, j-1)計(jì)算(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);
    }
}