#include <iostream>
#include <cassert>
#include <climits>
#include <cstring>
using namespace std;
#define MAX_SIZE 50
#define MAX_VAL 1000
// The dimensions of the chocolate
int r, c;
// The number of raisins on each piece of chocolate
short chocolate[MAX_SIZE][MAX_SIZE];
// The number of raisins in a rectangular sub-region subtended from the
// top-left corner of the chocolate.
int raisins[MAX_SIZE][MAX_SIZE];
// The minimum payment that Bonny must make for Peter to cut any
// rectangular sub-region of the chocolate.
int best[MAX_SIZE][MAX_SIZE][MAX_SIZE][MAX_SIZE];
/**
* Computes the smallest cost of cutting up the rectangular portion of
* the chocolate from (r1,c1) to (r2,c2).
*/
int solve(int r1, int c1, int r2, int c2)
{
if (best[r1][c1][r2][c2] == -1)
{
// We haven't computed this previously, so compute it now.
if (r1 == r2 && c1 == c2) {
// If we have a single cell left, then we're done:
// there's no additional cost.
best[r1][c1][r2][c2] = 0;
}
else {
// We try all the possible cuts, and see which results in
// the smallest total payment.
int best_payment = INT_MAX;
// First try the rows
for (int r = r1 + 1; r <= r2; r++)
{
int payment = solve(r1, c1, r - 1, c2) + solve(r, c1, r2, c2);
if (payment < best_payment)
best_payment = payment;
}
// Now try the columns
for (int c = c1 + 1; c <= c2; c++)
{
int payment = solve(r1, c1, r2, c - 1) + solve(r1, c, r2, c2);
if (payment < best_payment)
best_payment = payment;
}
// Determine how many raisins
int base_raisins = raisins[r2][c2];
if (r1 > 0)
base_raisins -= raisins[r1 - 1][c2];
if (c1 > 0)
base_raisins -= raisins[r2][c1 - 1];
if (r1 > 0 && c1 > 0)
base_raisins += raisins[r1 - 1][c1 - 1];
best[r1][c1][r2][c2] = best_payment + base_raisins;
}
}
return best[r1][c1][r2][c2];
}
int main()
{
cin >> r >> c;
assert(1 <= r && r <= MAX_SIZE);
assert(1 <= c && c <= MAX_SIZE);
// Read in the number of raisins on each piece of chocolate
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
{
cin >> chocolate[i][j];
assert(0 <= chocolate[i][j] && chocolate[i][j] <= MAX_VAL);
}
memset(raisins, -1, sizeof(raisins));
memset(best, -1, sizeof(best));
// First precompute the number of raisins on each rectangular
// sub-region subtended from the top-left corner of the chocolate.
raisins[0][0] = chocolate[0][0];
for (int i = 1; i < r; i++)
raisins[i][0] = chocolate[i][0] + raisins[i - 1][0];
for (int j = 1; j < c; j++)
{
raisins[0][j] = chocolate[0][j] + raisins[0][j - 1];
for (int i = 1; i < r; i++)
raisins[i][j] = chocolate[i][j] + raisins[i - 1][j] + raisins[i][j - 1] - raisins[i - 1][j - 1];
}
// Find the minimum payment for cutting up the whole slab of
// chocolate.
cout << solve(0, 0, r - 1, c - 1) << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
24960 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24832 KB |
Output is correct |
| 3 |
Correct |
14 ms |
24832 KB |
Output is correct |
| 4 |
Correct |
13 ms |
24832 KB |
Output is correct |
| 5 |
Correct |
13 ms |
24832 KB |
Output is correct |
| 6 |
Correct |
13 ms |
24832 KB |
Output is correct |
| 7 |
Correct |
14 ms |
24832 KB |
Output is correct |
| 8 |
Correct |
20 ms |
24832 KB |
Output is correct |
| 9 |
Correct |
25 ms |
24832 KB |
Output is correct |
| 10 |
Correct |
34 ms |
24832 KB |
Output is correct |
| 11 |
Correct |
28 ms |
24832 KB |
Output is correct |
| 12 |
Correct |
69 ms |
24832 KB |
Output is correct |
| 13 |
Correct |
104 ms |
24844 KB |
Output is correct |
| 14 |
Correct |
37 ms |
24832 KB |
Output is correct |
| 15 |
Correct |
124 ms |
24832 KB |
Output is correct |
| 16 |
Correct |
23 ms |
24832 KB |
Output is correct |
| 17 |
Correct |
57 ms |
24832 KB |
Output is correct |
| 18 |
Correct |
315 ms |
24848 KB |
Output is correct |
| 19 |
Correct |
511 ms |
24832 KB |
Output is correct |
| 20 |
Correct |
590 ms |
24952 KB |
Output is correct |
