问题描述:
要求求一个点(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>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int n, m, i, j, k;
int Min;
int map[101][101];
int sum[101][101];
int rt[101][101];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int t;
scanf("%d", &t);
while(t--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
Min = -1;
scanf("%d %d", &m, &n);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i = 1; i <= n; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j = 1; j <= m; j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d", &map[i][j]);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i = 1; i <= n; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(j = 1; j <= m; j++)
sum[i][j] = sum[i-1][j] + map[i][j];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i = 1; i <= n; i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
rt[i][1] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//计算(i, 1) 这个点作为Ketichen的距离和
for(j = 1; j <= n; j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for(k = 1; k <= m; k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
rt[i][1] += ( abs(i-j) + abs(k-1) ) * map[j][k];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(Min == -1 || rt[i][1] < Min)
Min = rt[i][1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//根据(i, j-1)计算(i, j)的值
for(j = 2; j <= m; j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
rt[i][j] = rt[i][j-1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(k = 1; k <= m; k++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%d blocks\n", Min);
}
}