Algorithm
Problem Name: beecrowd | 2785
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/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.
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;
}