1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#define inf INT_MAX / 2
using namespace std;
int n, v[9][9], s[9][9], f[9][9][9][9][16];
int sum (int x1, int y1, int x2, int y2)
{
int t = s[x2][y2] + s[x1 - 1][y1 - 1] - s[x2][y1 - 1] - s[x1 - 1][y2];
return t * t;
}
int dfs (int x1, int y1, int x2, int y2, int t)
{
if (~f[x1][y1][x2][y2][t])
return f[x1][y1][x2][y2][t];
if (!t)
return sum(x1, y1, x2, y2);
int res = inf;
for (int i = x1 + 1; i <= x2; i++)
res = min(res, sum(x1, y1, i - 1, y2) + dfs(i, y1, x2, y2, t - 1));
for (int i = x2 - 1; i >= x1; i--)
res = min(res, sum(i + 1, y1, x2, y2) + dfs(x1, y1, i, y2, t - 1));
for (int i = y1 + 1; i <= y2; i++)
res = min(res, sum(x1, y1, x2, i - 1) + dfs(x1, i, x2, y2, t - 1));
for (int i = y2 - 1; i >= y1; i--)
res = min(res, sum(x1, i + 1, x2, y2) + dfs(x1, y1, x2, i, t - 1));
f[x1][y1][x2][y2][t] = res;
return res;
}
int main ()
{
memset(f, -1, sizeof f);
cin >> n;
for (int i = 1; i <= 8; i++)
for (int j = 1; j <= 8; j++)
cin >> v[i][j];
for (int i = 1; i <= 8; i++)
for (int j = 1; j <= 8; j++)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v[i][j];
cout << dfs(1, 1, 8, 8, n - 1);
return 0;
}
|