以最低的能量到达目的地
给定N个点在一条与原点相距的直线上。此外，我们还得到了我们需要达到的终点。现在要达到顶点，我们应该有习量的能量，这一点也将给易的利润，作为能量的增加。现在我们需要找出我们应该从多少最小能量开始，这样才能从起点开始到达目的地。
例子:让我们有5个点，目标点是从原点开始的10个单位。
那么让我们先说第一点是从原点到一个单位，需要2个单位的能量，并给出3个单位的利润。
第二个点是从原点到2个单位，需要3个单位的能量，给出0单位的利润。
第三个点是从原点到4个单位，需要3个单位的能量，给出5个单位的利润。
第四点是从原点到8个单位，需要5个单位的能量，利润为0单位。
第五点是从原点到9个单位，需要1个单位的能量，并给出2个单位的利润。
现在，这个配置的答案是6。
解释:
因为如果我们从5个单位的能量开始
在第1点，我们有超过或等于2个单位的能量，因此利润1加能量，总能量是6。
在第2点，三个单位的能量将消失，只剩下3个单位。
在第3点，由于能量正好是3，利润就会增加，总能量变成5。
在第4点，所有5个单元都将消失，我们无法前进。
同样地，如果我们从6开始，其中一个可以通过点4和点4，在这里它将增加一个单位的能量，我们将到达目的地。
现在我们要找到最低限度的能源需求，开始到达最终目的地。
回答 2
Stack Overflow用户
发布于 2015-03-29 08:05:17
你把你的问题标记为动态规划。但我认为这更像是一个具有简单O(n)解的特殊问题。从相反的角度着手解决问题。对于给定的N=5点问题：
要到达目的地，必须在第五点至少有一个能量单位。现在假设用x能量单位输入第五个点，然后通过方程求出x的最小值：
X-1+2 >= 1 暗示x>=0 但x的最小值应该是1，以达到第5点本身。因此x= 1。
因此，你必须有至少一个单位的能量，而进入第五个点，以达到最终的目的地。同样，我们可以找到进入第四点所需的最小能量值如下：
X-5+0 >= 1 暗示x >= 6
因此，当你进入第4点时，你至少需要6个单位的能量才能到达目的地。
以这种方式继续下去，当你进入第一点时，你可以找到所需的最小能量。这将是所需的答案。
下面的工作java代码实现了这一点：
for(int i=0; i<n; i++){
req[i] = sc.nextInt();
profit[i] = sc.nextInt();
}
int minReq = 1;
for(int i=n-1; i>=0; i--){
int minEnter = minReq+req[i]-profit[i];
minEnter = Math.max(minEnter, req[i]);
minReq = minEnter;
}
System.out.println(minReq);Stack Overflow用户
发布于 2015-04-03 19:25:36
尝试：
int[] arr = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
int[] ar = new int[arr.Length];
int step = 1;
ar[arr.Length - 1] = -1;
for (int i = arr.Length - 2; i >= 0; i--)
{
if (arr[i] == 0)
ar[i] = -1;
else if (arr[i] >= step)
ar[i] = 1;
else
{
int min = int.MaxValue;
for (int j = 1; j <=arr[i]; j++)
{
if (ar[i+j]< min && ar[i+j]>0)
min = ar[i+j];
}
ar[i] =min+ 1;
}
step++;
}
Console.WriteLine(ar[0]);https://stackoverflow.com/questions/29326620
复制相似问题
腾讯云开发者
