# 使用reduce操作的金字塔形式（先升后降）连续数组

## 本文概述

``````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.``````

1.确定可以形成的最大高度的金字塔。

2.计算建造此类金字塔的成本。

## 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 chitranayal``````

## Python3

``````# 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``

• 回顶