#15. Platforms Jumping
Platforms Jumping
题目描述
有一条宽度为 的河流。河的左岸是 单元格,右岸是 单元格(更正式地说,这条河可以表示为一串从 到 编号,一共 单元格)。河上还有 个木制平台,其中 个平台的长度为 (因此 个平台占用了河上 个连续的单元格)。可以保证平台长度之和不超过 。
您现在站在 处,并希望以某种方式到达 。如果您站在位置 上,您可以跳到范围 中的任意位置。但是你并不喜欢水,所以你只能跳到属于某个木制平台的单元格。例如,如果是 ,您只能跳到下一个位置(如果它属于木制平台)。您可以假设单元格 和 属于木质平台。
您想知道的是,如果您可以将任意平台向左或向右移动任意次数(可能是零),只要它们不相交(但两个平台可以相碰),那么是否有可能从 到达 。这也意味着您不能改变平台的相对顺序。 注意,在开始跳跃之前,应先移动平台(换句话说,先移动平台,然后开始跳跃)。
例如,如果有 、 、 和 ,那么从 到达 的方法之一是遵循以下步骤:
输入格式
输入的第一行包含三个整数 和 ,分别是河流的宽度、平台的数量和跳跃的最大距离。
输入的第二行包含 个整数,$c_1,c_2,...,c_m(1 \leq c_i \leq n,\sum\limits_{i=1}^{m}c_i \leq n)$,其中 是 第 个平台的长度。
输出格式
如果无法从 到达 ,则在第一行打印 NO
。否则,第一行打印 YES
,第二行打印长度为 的数组 - 河单元格序列(不包括单元格 和单元格 )。
如果单元格 不属于任何平台,则 应为 。否则, 应等于单元格 所属平台的索引( 平台按输入顺序从 到 编号)。
注意所有等于 的 应构成长度为 的数组 的连续子块,所有等于 的 应构成长度为 的数组 的连续子块,...,所有等于 的 应构成长度为 的数组 的连续子块。 中 的最左端位置应大于 的最右端位置, 中 的最左端位置应大于 的最右端位置,..., 中 的最左端位置应大于 的最右端位置。
样例
样例输入 #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
提示
请看第一个例子:答案是 。你执行的跳跃序列是 。
再看第二个例子:如何放置平台并不重要,因为你总是可以从 跳到 。
再看第三个例子:答案是 。你的跳跃顺序是 。