最小伤害题解

【问题描述】

把儿站在一个NxN的方阵中最左上角的格子里。他可以从一个格子走到它右边和下边的格子里。每一个格子都有一个伤害值。他想在受伤害最小的情况下走到方阵的最右下角。

给定N与N×N方阵中的伤害值，求出最小伤害。

【样例输入】

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 1 0

0 0 0 0 1

【样例输出】

【解题思路】

这道题与过河卒（NOIP2002)的思路一样，且比过河卒更加容易（少了马的控制），典型的递推问题，用DP解决。

【动规方程】

f[i,j]:=min(f[i-1,j],f[i,j-1])+a[i,j](2<=i<=n，2<=j<=n);

【边界条件】

f[1,1]:=a[1,1];f[1,i]:=f[1,i-1]+a[1,i](2<=i<=n);f[i,1]:=f[i-1,1]+a[i,1](2<=i<=n);

注意！最上边和最左边的两排也要先赋值！

【代码实现】

uses math;//这里用了数学库，就可以直接调用min函数，数学库中有许多有用的函数，就不必自己手写了。
var a,f:array[1..1000,1..1000] of longint;
    i,j,n:longint;
begin
 readln(n);
 for i:=1 to n do
  for j:=1 to n do
   read(a[i,j]);
//边界赋值
 f[1,1]:=a[1,1];
 for i:=2 to n do
  begin
   f[1,i]:=f[1,i-1]+a[1,i];
   f[i,1]:=f[i-1,1]+a[i,1];
  end;
//动态规划
 for i:=2 to n do
  for j:=2 to n do
   f[i,j]:=min(f[i-1,j],f[i,j-1])+a[i,j];
 writeln(f[n,n]);
end.

最小伤害

最小伤害 题解