我该如何编码呢？基于动态编程的算法是什么？ [英] How Do I Code This? On Which Algorithm Of Dynamic Programing Is It Based On?

问题描述

贵公司正在p [0]，p [1]，...，p [n-1]点的直线铁路线上建造手机信号塔。公司必须为工人建造临时房屋，并希望确保两个条件：（i）从每个点p [i]，到最近房屋的距离应至多为k; （ii）临时房屋的数量应尽可能小。

输入：输入将由若干行组成，每行包含一个如下数字：

第一行将具有数字n（0
第二行将具有数字k（0
接下来的n行将包含值

p [0]

p [1]

：

p [n1 ]（每行一个值）

注意：数字p [0]，p [1]，...，p [n-1]未排序，并且对于i的每个值，0< ; p [1] - GT;< 10n。

输出：编写一个程序，按照增加的顺序打印构建房屋的（整数）位置，每行一个整数。您还必须确保您的程序满足上述条件（i）和（ii）。您的程序应打印NOTHING ELSE。

下面给出了一些示例输入和输出。请注意，程序的输出不需要与这些输出完全匹配 - 重要的是满足条件（i）和（ii）并且数字以增加的顺序打印。

样本输入1：

5

3

15

8

9

1

12

样品输出1：

1

10

15

解决方案

我们不做你的作业：它是有原因的。它就是为了让你思考你被告知的事情，并试着理解它。它也在那里，以便您的导师可以识别您身体虚弱的区域，并将更多的注意力集中在补救措施上。



亲自尝试，你可能会发现它不是和你想的一样困难！



如果遇到具体问题，请询问相关问题，我们会尽力提供帮助。但是我们不会为你做这一切！



所以想想你如何为一个简单的系统手工完成它，并从那里开始工作。 / BLOCKQUOTE>

Your company is building cell-phone towers along a straight railway line at points p[0], p[1], …, p[n-1]. The company must construct temporary houses for workers, and wants to ensure two conditions: (i) from every point p[i], the distance to the nearest house should be at most k; and (ii) the number of temporary houses should be as small as possible.
Input: The input will consist of several lines, each containing one number as follows:
The first line will have the number n (0 < n < 100000)
The second line will have the number k (0 < k < n)
The next n lines will contain the values
p[0]
p[1]
:
p[n1] (one value per line)
Note: The numbers p[0], p[1], …, p[n-1] are NOT sorted, and for each value of i, 0 <p[i]>< 10n.
Output: Write a program that prints the (integer) locations at which to construct houses, one integer per line, in INCREASING order. You must also ensure that your program satisfies conditions (i) and (ii) above. Your program should print NOTHING ELSE.
Some sample inputs and outputs are given below. Note that the outputs of your program need not match these outputs exactly – what matters is that conditions (i) and (ii) are satisfied and that the numbers are printed in INCREASING order.
Sample input 1:
5
3
15
8
9
1
12
Sample output 1:
1
10
15

解决方案

We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think!

If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!

So think about how you would do it by hand for a simple system, and work from there.

这篇关于我该如何编码呢？基于动态编程的算法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！