给定一个N×N的正方形网格,设其左上角为起点◎,坐标为(1,1),X轴向右为正,Y轴向下为正,每个方格边长为1,如图所示.一辆汽车从起点◎出发驶向右下角终点▲,其坐标为(N,N).在若干个网格交叉点处,设置了油库,可供汽车在行驶途中加油.汽车在行驶过程中应遵守如下规则:

　　(1)汽车只能沿网格边行驶,装满油后能行驶K条网格边.出发时汽车已装满油,在起点与终点处不设油库.

　　(2)汽车经过一条网格边时,若其X坐标或Y坐标减小,则应付费用B,否则免付费用.

　　(3)汽车在行驶过程中遇油库则应加满油并付加油费用A.

　　(4)在需要时可在网格点处增设油库,并付增设油库费用C(不含加油费用A)

　　N,K,A,B,C均为正整数,且满足约束:2≤N≤100, 2≤K≤10

　　求出汽车从起点出发到达终点的最少费用.

　　示 例

　　数据输入:由文件input.txt提供输入数据.文件的第一行是N,K,A,B,C的值.第二行起是一个N*N 的0-1 方阵,每行N 个值,至N+1 行结束.方阵的第i 行第j 列处的值为1 表示在网格交叉点(i,j)处设置了一个油库,为0 时表示未设油库.各行相邻两个数以空格分隔.

　　输入文件示例 输出文件示例

　　input.txt output.txt

　　9 3 2 3 6 12

　　0 0 0 0 1 0 0 0 0

　　0 0 0 1 0 1 1 0 0

　　1 0 1 0 0 0 0 1 0

　　0 0 0 0 0 1 0 0 1

　　1 0 0 1 0 0 1 0 0

　　0 1 0 0 0 0 0 1 0

　　0 0 0 0 1 0 0 0 1

　　1 0 0 1 0 0 0 1 0

　　0 1 0 0 0 0 0 0 0

　　解 题 思 路

　　采用的是动态规划的思想来解题,用备忘录的方法进行递归,递归的式子后面写出.

　　不能直接以汽车行驶的费用为目标来进行动态规划,因为最优子结构性质得不到证明.

　　所以必须把油量和费用一起考虑,作为动态规划的对象,此时就有了最优子结构性质.

　　最优子结构性质的证明

　　证明:假设路径M是从起点◎到终点▲的一条最小费用路径,P(x,y)是M经过的一个点(非加油站),且油量和费用为(g,c),现假设有一条新路径Q从起点◎到点P(x,y),使得其在P(x,y)点的油量和费用为(g,c'),其中c'备忘录递归

　　刚开始的时候为每个网格点P(x,y)建立一个记录,初始化时,为该记录存入一个特殊值W,表示汽车未行驶过.那么在汽车行驶过程中,对每个待求的汽车最小费用值COST,先查看其相应的记录项C,如果存储的是初始值W,那么表示这个点P(x,y)是第一次遇到,此时计算出该点的最小费用值,并保存在其相应的记录项中,以备以后查看.若记录项C中存储的不是初始值W,那么表示该问题已经求解过了,其相应的记录项中存储的就是该点的最小费用值COST,此时要取出记录项C的值跟最新的计算出的COST进行比较,取其最小的那个数存入到C中.依此建立记录项C的值,当程序递归完成时,我们也得到了汽车行驶到(n,n)的最小费用值COST.

　　备忘录递归式

　　C(x,y,g)表示在(x,y)位置上,剩余油量为g时的所耗费用.

　　C(x,y,g)=min{C(x+s[i][0],y+s[i][1],0)+s[i][2]}.其中0≤i≤3.

　　用3维数组s={{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}}表示汽车的行驶方向.

　　当行驶到油库时,要加满油,故有: C(x,y,g)= C(x,y,K)= C(x,y,g) + A.

　　当油用尽但还没到油库时,要建立油库,并且加油,故有: C(x,y,0)= C(x,y,K)= C(x,y,0) + C + A.