蒜头君的坐骑

admin/2020-03-14/ 分类:明星发型/阅读:
蒜头君有一只坐骑,人马。 一天,蒜头君骑着他的坐骑走上了一片 n×m 的大年夜荒野,一末尾时,蒜头君在 (1,1) 点,他要前去(n,m) 点,蒜头君的人马每次可以向右或向下移动一格。然 ...

  蒜头君有一只坐骑,人马。

  一天,蒜头君骑着他的坐骑走上了一片 n×m 的大年夜荒野,一末尾时,蒜头君在 (1,1) 点,他要前去(n,m) 点,蒜头君的人马每次可以向右或向下移动一格。然则这片荒野其实不宁静,除终点和终点外每个点都有一只怪物会攻击蒜头君。

  然则蒜头君的人马弱小非常,它会先对怪物形成一致于它进击力的毁伤,然后蒜头君才会遭到怪物的进击,毁伤一致于怪物的进击力。然先人马再进击怪物,怪物再进击蒜头君,直至怪物逝世去,假定每个怪物具有相反的体力。

  另外,蒜头君的人马还有一个弱小非常的身手,应用该身手会使蒜头君接上去 k 次移动,每次移动后添加一致于移动到的格子的怪物的进击力,k 次移动后,人马进击力恢复至初始进击力。人马必须在以后一个身手释放完后才可以释放下一个身手,且一共可释放身手的次数有限,那么试问蒜头君从终点到终点起码遭到若干点毁伤。

  留心:蒜头君的体力是有限的。

  第一行六个正整数 n,m,t,k,h,atk,表现地图长度、宽度、人马身手可应用次数、人马身手继续移动次数、每只怪物的体力和人马的初始进击力。保证 n+m?1≥t×k。

  接上去 n 行,每行 m 个整数,表现每个点的怪物的进击力。保证 (1,1) 点、(n,m) 点为 0,其他点为正整数。

  输入一个整数,表现蒜头君遭到的最小毁伤。

  关于 30% 的测试数据,满足 1≤n,m≤10, 1≤t≤3, 1≤k≤3;

  关于 60% 的测试数据,满足 1≤n,m≤100, 1≤t≤10, 1≤k≤5;

  关于 100% 的测试数据,满足1≤n,m≤500, 1≤t≤10, 1≤k≤5, 1≤atk≤h≤100, 1≤ 怪物进击力 ≤100。

  第一次做相似的题目,举动当作积累了。

  思维不难,就是全部DP,局部搜刮。(据说还有一种有后效性的DP是全部DP,局部高斯消元)

  令为行列第次应用身手的最小毁伤。

  当不释放身手时,直接转移:(cnt为原始进击需求打的次数)

  搜刮释放身手能抵达的答案并更新dp。

  为了确保如许是对的,有如许一句话“应用该身手会使蒜头君接上去 k 次移动,每次移动后添加一致于移动到的格子的怪物的进击力”,也就是说,放身手是延续的。而k值的范围又小。

  全部复杂度,基天禀过

  code:

  2018.6.23

阅读:

推荐文章

Recommend article
188bet
微信二维码扫一扫
关注微信公众号
联系QQ:329435596 邮箱:329435596@qq.com Power by DedeCms
二维码
意见反馈 二维码