#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mn = 50;
int dp[mn][mn][mn][mn];
int vvi[mn + 1][mn + 1] = {}, qsum[mn + 1][mn + 1] = {};
int ans(int x1, int y1, int x2, int y2) {
if (x1 == x2 && y1 == y2) {
return 0;
}
if (dp[x1][y1][x2][y2] != -1) {
return dp[x1][y1][x2][y2];
}
int cur =
qsum[x2 + 1][y2 + 1] - qsum[x2 + 1][y1] - qsum[x1][y2 + 1] + qsum[x1][y1];
dp[x1][y1][x2][y2] = LLONG_MAX;
if (x1 != x2) {
for (int i = x1; i < x2; i++) {
dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], cur + ans(x1, y1, i, y2) +
ans(i + 1, y1, x2, y2));
}
}
if (y1 != y2) {
for (int i = y1; i < y2; i++) {
dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], cur + ans(x1, y1, x2, i) +
ans(x1, i + 1, x2, y2));
}
}
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << cur << " "
// << dp[x1][y1][x2][y2] << "\n";
return dp[x1][y1][x2][y2];
}
signed main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> vvi[i][j];
qsum[i][j] +=
qsum[i - 1][j] + qsum[i][j - 1] - qsum[i - 1][j - 1] + vvi[i][j];
}
memset(dp, -1, sizeof dp);
cout << ans(0, 0, n - 1, m - 1) << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |