srcmini本文概述
我们连续排列了N块(其中N> 2)个不同高度的石头。任务是从给定的石头阵列中制成金字塔。在金字塔中, 宝石的高度从1开始, 增加1, 直到达到某个值x, 然后减小1, 直到再次达到1, 即宝石应为1, 2, 3, 4…x – 1, x , x – 1, x – 2…1.除金字塔外的所有其他石头的高度都应为0。我们不能将任何石头从其当前位置移开, 但是, 通过支付1的费用, 我们可以减少石头的高度。我们希望将建造金字塔的成本降至最低。输出建造该金字塔的最低成本。
例子：
Input : 1 2 3 4 2 1
Output : 4
The best pyramid that can be formed in this case is:
1 2 3 2 1 0
The cost is thus:
(4 - 2) + (2 - 1) + (1 - 0) = 4
Input : 1 5 2
Output : 4
We make a pyramid 1 2 1
Input : 1 2 1
Output : 0
We already have a pyramid, we do not need to do any
further construction.通过使用简单的逻辑, 我们可以证明建造成本最低的金字塔将是最大高度的金字塔。同样, 两个高度相同的庙宇的建造成本也相同。
可以显示如下：
假设将所有石头拆除到0高度的成本为x。
假设将高度为h的太阳穴拆除为高度0的成本为y。
然后, 如果有可能用给定的石头建造一个高度为h的太阳穴, 其成本将为x – y。
通过使用此方法, 我们可以将方法简化为两个主要步骤：
1.确定可以形成的最大高度的金字塔。
2.计算建造此类金字塔的成本。
假设我们知道金字塔的放置位置, 那么第二步可以以O(N)时间复杂度完成。
因此, 我们的重点应该放在降低步骤1的时间复杂度上。
天真的方法
对于数组中的每个位置, 我们可以假定金字塔从该点开始。然后, 我们发现从1开始构造最大高度的庙宇的成本, 直到不可能达到更高的高度为止, 也就是说, 假设高度为1的金字塔最大, 然后假设高度为2, 依此类推。然后从所有这些成本中选择最低成本。
该方法使用时间复杂度为O(N ^ 3)。
改进方法
对于每个位置, 假设它是太阳穴的中心。移至该点的左右, 并尝试找到寺庙的最大高度。
这可以通过将位置i处的镜腿的最大高度设置为H(i)来实现, 其中H(i)是该点上的石头的高度。然后, 我们向左移动。如果此时石材的高度小于H(i)– 1, 则我们将最大高度设置为H(i – 1)+1。这样, 我们确定每个位置的最大高度。
该方法使用时间复杂度为O(N ^ 2)。
动态规划方法
通过稍微修改上述算法, 我们可以尝试获得O(N)方法。从左侧开始, 然后向右移动, 找到可以在该位置创建的最大高度金字塔。假设该位置右侧数组的一部分是左侧的镜像。如果H(i)是位置i处石头的高度, 则maxHeight(i)= Minimum(H(i), i, maxHeight(i – 1))
可以解释如下：
最大可能的高度不能超过H(i), 因为我们只能减小石头的高度, 而不能增加。
最大可能的高度不能超过i, 因为金字塔必须从高度1开始。
最大可能的高度不能超过石头之前的最大可能高度– 1, 因为每步石头必须增加1。
我们计算从右到左的相似值。然后, 我们为每个位置取这些值中的最小值。然后, 通过确定最大值, 我们可以计算出构建金字塔的最小成本。
C ++
//Program to find minimum cost for pyramid
//from given array
#include <iostream>
using namespace std;
#define ull unsigned long long
//Returns minimum cost to form a pyramid
ull minPyramidCost(ull arr[], ull N)
{
//Store the maximum possible pyramid height
ull *left = new ull[N];
ull *right = new ull[N];
//Maximum height at start is 1
left[0] = min(arr[0], (ull)1);
//For each position calculate maximum height
for ( int i = 1; i <N; ++i)
left[i] = min(arr[i], min(left[i - 1] + 1, (ull)i + 1));
//Maximum height at end is 1
right[N - 1] = min(arr[N - 1], (ull)1);
//For each position calculate maximum height
for ( int i = N - 2; i>= 0; --i)
right[i] = min(arr[i], min(right[i + 1] + 1, N - i));
//Find minimum possible among calculated values
ull tot[N];
for ( int i = 0; i <N; ++i)
tot[i] = min(right[i], left[i]);
//Find maximum height of pyramid
ull max_ind = 0;
for ( int i = 0; i <N; ++i)
if (tot[i]> tot[max_ind])
max_ind = i;
//Calculate cost of this pyramid
ull cost = 0;
ull height = tot[max_ind];
//Calculate cost of left half
for ( int x = max_ind; x>= 0; --x)
{
cost += arr[x] - height;
if (height> 0)
--height;
}
//Calculate cost of right half
height = tot[max_ind] - 1;
for ( int x = max_ind + 1; x <N; ++x)
{
cost += arr[x] - height;
if (height> 0)
--height;
}
return cost;
}
//Driver code
int main()
{
ull arr[] = {1, 2, 3, 4, 2, 1};
ull N = sizeof (arr)/sizeof (arr[0]);
cout <<minPyramidCost(arr, N);
return 0;
}Java
//Java program to find minimum cost for
//pyramid from given array
import java.util.*;
class GFG{
//Returns minimum cost to form a pyramid
static int minPyramidCost( int arr[], int N)
{
//Store the maximum possible pyramid height
int left[] = new int [N];
int right[] = new int [N];
//Maximum height at start is 1
left[ 0 ] = Math.min(arr[ 0 ], 1 );
//For each position calculate maximum height
for ( int i = 1 ; i <N; ++i)
left[i] = Math.min(arr[i], Math.min(left[i - 1 ] + 1 , i + 1 ));
//Maximum height at end is 1
right[N - 1 ] = Math.min(arr[N - 1 ], 1 );
//For each position calculate maximum height
for ( int i = N - 2 ; i>= 0 ; --i)
right[i] = Math.min(arr[i], Math.min(right[i + 1 ] + 1 , N - i));
//Find minimum possible among
//calculated values
int tot[] = new int [N];
for ( int i = 0 ; i <N; ++i)
tot[i] = Math.min(right[i], left[i]);
//Find maximum height of pyramid
int max_ind = 0 ;
for ( int i = 0 ; i <N; ++i)
if (tot[i]> tot[max_ind])
max_ind = i;
//Calculate cost of this pyramid
int cost = 0 ;
int height = tot[max_ind];
//Calculate cost of left half
for ( int x = max_ind; x>= 0 ; --x)
{
cost += arr[x] - height;
if (height> 0 )
--height;
}
//Calculate cost of right half
height = tot[max_ind] - 1 ;
for ( int x = max_ind + 1 ; x <N; ++x)
{
cost += arr[x] - height;
if (height> 0 )
--height;
}
return cost;
}
//Driver code
public static void main(String[] args)
{
int arr[] = { 1 , 2 , 3 , 4 , 2 , 1 };
int N = arr.length;
System.out.print(minPyramidCost(arr, N));
}
}
//This code is contributed by chitranayalPython3
# Program to find minimum cost for pyramid
# from given array
# Returns minimum cost to form a pyramid
def minPyramidCost(arr: list , N):
# Store the maximum possible pyramid height
left = [ 0 ] * N
right = [ 0 ] * N
# Maximum height at start is 1
left[ 0 ] = min (arr[ 0 ], 1 )
# For each position calculate maximum height
for i in range ( 1 , N):
left[i] = min (arr[i], min (left[i - 1 ] + 1 , i + 1 ))
# Maximum height at end is 1
right[N - 1 ] = min (arr[N - 1 ], 1 )
# For each position calculate maximum height
for i in range (N - 2 , - 1 , - 1 ):
right[i] = min (arr[i], min (right[i + 1 ] + 1 , N - i))
# Find minimum possible among calculated values
tot = [ 0 ] * N
for i in range (N):
tot[i] = min (right[i], left[i])
# Find maximum height of pyramid
max_ind = 0
for i in range (N):
if tot[i]> tot[max_ind]:
max_ind = i
# Calculate cost of this pyramid
cost = 0
height = tot[max_ind]
# Calculate cost of left half
for x in range (max_ind, - 1 , - 1 ):
cost + = arr[x] - height
if height> 0 :
height - = 1
# Calculate cost of right half
height = tot[max_ind] - 1
for x in range (max_ind + 1 , N):
cost + = arr[x] - height
if height> 0 :
height - = 1
return cost
# Driver Code
if __name__ = = "__main__" :
arr = [ 1 , 2 , 3 , 4 , 2 , 1 ]
N = len (arr)
print (minPyramidCost(arr, N))
# This code is contributed by
# sanjeev2552输出如下：
4这种方法运行时间为O(N)。
评论前必须登录！
注册