## Algorithm

Problem Name: beecrowd | 2785

# Pyramid

By OBI Brasil

Timelimit: 1

In the deposit of the factory, leaning against a wall, there is a matrix of N lines by N columns of stacked boxes. Each box has an associated positive integer weight. The factory inspector needs to remove some boxes from the matrix so as to leave a kind of box pyramid satisfying the following restrictions:

• If a box is in the pyramid, the box just below it should also be in the pyramid;
• In the i-th line of boxes (line 1 is that of the top of the matrix), the pyramid must have exactly i consecutive boxes.
Given the weights of all boxes in the matrix, your program must calculate the minimum total weight a pyramid might have if the inspector pulls out some boxes according to the above restrictions.

## Input

The first line of the input contains an integer N (1 ≤ N ≤ 100), indicating the dimension of the matrix. The next N lines each contain N integers representing the weights of the boxes in each row of the array of boxes.

The values ​​of the array elements are between 1 and 100, inclusive.

## Output

Your program must to produce an unique line, containing an integer, indicating the total weight that the pyramid might have.

 Input Samples Output Samples 3 5 2 4 3 6 7 10 5 10 36

 4 45 8 3 1 1 10 5 67 4 4 3 18 10 4 7 12 62

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 10;
const int INF = 1e9;

int soma[MAXN][MAXN], matriz[MAXN][MAXN], dp[MAXN][MAXN], N;

int calcula(int id, int a, int b) { return soma[id][b] - soma[id][a - 1]; }

int solve(int linha, int pos) {
if (linha == N + 1) return 0;
if (dp[linha][pos] != -1) return dp[linha][pos];
if (pos  < = 0 || linha + pos - 1 > N) return dp[linha][pos] = INF;
int agora = calcula(linha, pos, pos + linha - 1);
int proxima = min(solve(linha + 1, pos - 1), solve(linha + 1, pos));
return dp[linha][pos] = agora + proxima;
}

int main() {
memset(dp, -1, sizeof(dp));
scanf("%d", &N);
for (int i = 1; i  < = N; i++) {
for (int j = 1; j  < = N; j++) {
scanf("%d", &matriz[i][j]);
soma[i][j] = soma[i][j - 1] + matriz[i][j];
}
}
int resposta = solve(1, 1);
for (int i = 2; i  < = N; i++) resposta = min(resposta, solve(1, i));
printf("%d\n", resposta);
return 0;
}

``````
Copy The Code &
Advertisements