题目
青蛙去找瓜瓜，青蛙在1号位置，瓜瓜在n号位置。
青蛙一次可以走 k 步，走1 ~ k 步耗费的体力不同。
问青蛙找到瓜瓜耗费的最小体力是多少？
输入
第一行输入n、k、op，op = 1时，需要计算耗费最小体力的路径一共有多少条；
第二行输入k个数，分别是走 1 ~ k 步耗费的体力 a[ i ]。
输出
如果op = 0，输出1个数，为最小体力；如果op = 1，输出最小体力后，输出路径数。
数据范围
n最大到了1e9，好像
思路
如果想偷点分，不会op = 1的情况，就先别管它了！
数据范围太大，处理不了，也别管它了！
然后经过一顿骚操作，变成了一个简单的dp问题：
f [ i ] 为走到第 i 号位置，需要耗费的最小体力。
f[ i ] = min( a[ j ] + f [ i - j ] )，1 <= j <= k。
然后解决数据范围大的问题：
我们刚才 f 数组的大小是n，但我们可以发现，其实状态转移的时候只需要 f[ i - k ] ~ f [i - 1 ]，其实我考虑可以用队列实现这个数组？
然后解决 op = 1 的问题，在每次求 f 的时候，在循环里找到min( a[ j ] + f [ i - j ] )，然后统计minn的个数，每一个乘 f [ i - j ]的num，最后求和就是f [ i ]的num。
PS:虽然我嘴炮了这么多，其实我考试的时候只写了个暴力dp，拿了40分，后头的都是review的时候想的，没实现23333
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
