题目描述

给出一个数组由$N$个整数$A_1，A_2，...，A_N$组成的数组$A$ （下标从1开始），和一个整数$B$。这个整数$B$表示，在数组$A$ 中，从任意位置（假设数组下标为$i$）可以跳到以数组$A$中$i+1，i+2，…，i+B$为下标的任何一个位置，只要你可以跳到数组$A$ 中的这个位置。并且，如果你站在下标为$i$的位置上，你需要付$A_i$个硬币。如果$A_i$是-1，表示不能跳到数组中下标为$i$ 的位置。

现在，从数组$A$中下标为1的位置开始，你需要付最少的硬币，到达下标为$N$的位置。返回支付最少硬币到达下标$N$的路径（从1开始直到$N$），用数组表示。

如果存在相同花费的多条路径，返回字典序最小的路径。

如果不能够到达下标N的位置，那么返回一个空的数组。

输入格式

第一行1个整数$n$,表示$A$数组元素个数

第二行，$n$个整数，表示$A$数组元素，空格隔开

第三行，一个整数$B$

输出格式

返回字典序最小的路径,如果没有，返回nill

5
1 2 3 4 5
2

1 3 5

解释：9是最小的花费

5
1 2 4 -1 2
1

nill

解释：不存在从1到n的路径

数据范围

1、路径$P_{a_1}, P_{a_2}, ..., P_{a_n}$比$P_{b_1}, P_{b_2}, ..., P_{b_m}$的字典序小，当且仅当使得$P_{a_i}$与$P_{b_i}$不同的第一个$i，P_{a_i} < P_{b_i}$；如果不存在这样的$i$，那么 $n < m$。

2、$A[0]>= 0。A[1], ..., A[N-1]$ （如果存在）在[-1, 100]的范围内。

3、$A$的长度在[1, 1000]的范围内。

4、$B$在[1, 100]的范围内。

来源

lintcode 866