#15. Platforms Jumping

Platforms Jumping

题目描述

有一条宽度为 nn 的河流。河的左岸是 00 单元格,右岸是 n+1n+1 单元格(更正式地说,这条河可以表示为一串从 00n+1n+1 编号,一共 n+2n+2 单元格)。河上还有 mm 个木制平台,其中 ii 个平台的长度为 cic_i (因此 ii 个平台占用了河上 cic_i 个连续的单元格)。可以保证平台长度之和不超过 nn

您现在站在 00 处,并希望以某种方式到达 n+1n+1 。如果您站在位置 xx 上,您可以跳到范围 [x+1,x+d][x+1,x+d] 中的任意位置。但是你并不喜欢水,所以你只能跳到属于某个木制平台的单元格。例如,如果是 d=1d=1 ,您只能跳到下一个位置(如果它属于木制平台)。您可以假设单元格 00n+1n+1属于木质平台。

您想知道的是,如果您可以将任意平台向左或向右移动任意次数(可能是零),只要它们不相交(但两个平台可以相碰),那么是否有可能从 00 到达 n+1n+1 。这也意味着您不能改变平台的相对顺序。 注意,在开始跳跃之前,应先移动平台(换句话说,先移动平台,然后开始跳跃)。

例如,如果有 n=7n=7m=3m=3d=2d=2c=[1,2,1]c=[1,2,1] ,那么从 00 到达 88 的方法之一是遵循以下步骤:

image

n=7n=7

输入格式

输入的第一行包含三个整数 nmn、md(1n,m,d1000,mn)d(1 \leq n,m,d \leq 1000,m \leq n),分别是河流的宽度、平台的数量和跳跃的最大距离。

输入的第二行包含 mm 个整数,$c_1,c_2,...,c_m(1 \leq c_i \leq n,\sum\limits_{i=1}^{m}c_i \leq n)$,其中 cic_i 是 第 ii 个平台的长度。

输出格式

如果无法从 00 到达 n+1n+1 ,则在第一行打印 NO。否则,第一行打印 YES,第二行打印长度为 nn 的数组 aa - 河单元格序列(不包括单元格 00 和单元格 n+1n+1 )。

如果单元格 ii 不属于任何平台,则 aia_i 应为 00 。否则, aia_i 应等于单元格 ii 所属平台的索引( 平台按输入顺序从 11mm 编号)。

注意所有等于 11aia_i 应构成长度为 c1c_1 的数组 aa 的连续子块,所有等于 22aia_i 应构成长度为 c2c_2 的数组 aa 的连续子块,...,所有等于 mmaia_i 应构成长度为 cmc_m 的数组 aa 的连续子块。 aa22 的最左端位置应大于 11 的最右端位置, aa33 的最左端位置应大于 22 的最右端位置,..., aamm 的最左端位置应大于 m1m-1 的最右端位置。

样例

样例输入 #1

7 3 2
1 2 1

样例输出 #1

YES
0 1 0 2 2 0 3

样例输入 #2

10 1 11
1

样例输出 #2

YES
0 0 0 0 0 0 0 0 0 1

样例输入 #3

10 1 5
2

样例输出 #3

YES
0 0 0 0 1 1 0 0 0 0

提示

请看第一个例子:答案是 [0,1,0,2,2,0,3][0,1,0,2,2,0,3] 。你执行的跳跃序列是 0245780→2→4→5→7→8

再看第二个例子:如何放置平台并不重要,因为你总是可以从 00 跳到 1111

再看第三个例子:答案是 [0,0,0,0,1,1,0,0,0,0][0,0,0,0,1,1,0,0,0,0]。你的跳跃顺序是 056110→5→6→11