jzoj 1571. 【普及模拟】过河

发布于 2019-03-20  8 次阅读


人们通过在石头上跳跃从河的一边到达另一边。

 

 

 

如图所示,我们把石头的形状看作是一个正方形,一共有n行,这里n=5。

 

在游戏中,人们有两种方法:一种是普通跳跃和快速跳跃,快速跳跃的次数不得超过M。普通跳跃中,他们能从当前石头跳到下一行的某个石头,而快速跳跃使得他们能从一个石头跳到下一行的下一行某个石头处。出发的一边的下一行是第一行,第N行的下一行是对岸。

 

为了保证游戏的安全性,我们需要考虑每一次跳跃的危险系数,每个石头有一个自身的危险值,每次跳跃的危险系数计算方法如下:

 

(当前石头的危险系数+下一个到达石头的危险系数)*(水平距离)        

 

计算方法不考虑跳跃的种类,水平距离是两个石头所在列的差的绝对值,从岸边跳到某个石头或者从石头跳到岸边的危险系数为0。

 

写一个程序,给定N和M的值和每行石头的位置以及危险系数,计算从起始边到对岸最小的危险系数总和。输入保证一定可以到达对岸。

 

输入

第一行包含两个整数N,M,N表示行数,M表示最多可以使用快速跳跃的次数,N,M满足2<=N<=150,0<=M<=(n+1)/2

接下来N行,第i行首先是一个整数K­_i(0<=K_i<=10),表示这一行石头的数量,然后是2*K­_i的整数,表示石头的所在列和危险系数(1<=列的值,危险系数<=1000)

输出

    输出一个整数表示最小危险系数总和的值。
有毒的动态规划,f[i,j,k]表始从第i行第j个石头用了k次超级跳用的最小价值
f[i,j,k]=min{f[i-2,j,k-1],f[i-1,j,k]}

 

]]>