hdu 5492 Find a path（dp+少量数学）2015 ACM/ICPC Asia Regional Hefei Online

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：

给出一个n*m的地图，要求从左上角(0, 0)走到右下角(n-1, m-1)。

地图中每个格子中有一个值。然后根据这些值求出一个最小值。

这个最小值要这么求——

这是我们从起点走到终点的路径，其中N是地图的长，M是地图的宽，Ai表示路径中第i个点的值，Aavg表示路径中所有的点的值的平均值。要求这个式子的值最小。

我们可以将它转化为

好了，推到这里，我们需要的数学知识就结束了（实际上以我的数学知识也只能做到这里了……）。然后dp就好了——

Dp[i][j][k]，i表示第i行，j表示第j列，k表示所有Ai的和，这个里面保存的是所有的值。

然后dp下去就好了.

dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k-mp[i-1][j]]+mp[i][j]*mp[i][j], dp[i][j][k-mp[i][j-1]]+mp[i][j]*mp[i][j]);

具体见代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int M = ;
const int Mod = ;
const int N = ;
const int NN = ; int t, n, m;
int dp[N][N][NN], mp[N][N];
int ans; int Min(int x, int y)
{
if(x == -) return y;
return x < y ? x : y;
} void Dp()
{
memset(dp, -, sizeof(dp));
dp[][][mp[][]] = mp[][]*mp[][];
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
if(i- >= )
{
for(int k = mp[i][j]; k < NN; k++)
{
if(dp[i-][j][k-mp[i][j]] != -)
{
dp[i][j][k] = Min(dp[i][j][k], dp[i-][j][k-mp[i][j]]+mp[i][j]*mp[i][j]);
}
}
}
if(j- >= )
{
for(int k = mp[i][j]; k < NN; k++)
{
if(dp[i][j-][k-mp[i][j]] != -)
{
dp[i][j][k] = Min(dp[i][j][k], dp[i][j-][k-mp[i][j]]+mp[i][j]*mp[i][j]);
}
}
}
}
}
} int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &t);
for(int tm = ; tm <= t; tm++)
{
scanf("%d%d", &n, &m);
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++) scanf("%d", &mp[i][j]);
}
Dp();
ans = -;
for(int i = ; i < NN; i++)
{
if(dp[n-][m-][i] != -)
{
int mid = (n+m-)*dp[n-][m-][i]-i*i;
if(ans == -) ans = mid;
else ans = ans < mid ? ans : mid;
}
}
printf("Case #%d: %d\n", tm, ans);
}
return ;
}