#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 55;
int dp[N][N][N][N];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
vector<vector<int>> psum = a;
for (int i = 0; i < n; ++i) {
for (int j = 1; j < m; ++j) {
psum[i][j] += psum[i][j - 1];
}
}
for (int j = 0; j < m; ++j) {
for (int i = 1; i < n; ++i) {
psum[i][j] += psum[i - 1][j];
}
}
memset(dp, 0x3f, sizeof(dp));
for (int il = n - 1; il >= 0; --il) {
for (int ir = il; ir < n; ++ir) {
for (int jl = m - 1; jl >= 0; --jl) {
for (int jr = jl; jr < m; ++jr) {
int sum = (il && jl ? psum[il - 1][jl - 1] : 0) + psum[ir][jr]
- (il ? psum[il - 1][jr] : 0) - (jl ? psum[ir][jl - 1] : 0);
if (il == ir && jl == jr) {
dp[il][ir][jl][jr] = 0;
continue;
}
for (int im = il; im < ir; ++im) {
dp[il][ir][jl][jr] = min(dp[il][ir][jl][jr],
dp[il][im][jl][jr] + dp[im + 1][ir][jl][jr] + sum);
}
for (int jm = jl; jm < jr; ++jm) {
dp[il][ir][jl][jr] = min(dp[il][ir][jl][jr],
dp[il][ir][jl][jm] + dp[il][ir][jm + 1][jr] + sum);
}
}
}
}
}
cout << dp[0][n - 1][0][m - 1] << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
36188 KB |
Output is correct |
2 |
Correct |
5 ms |
36184 KB |
Output is correct |
3 |
Correct |
4 ms |
36188 KB |
Output is correct |
4 |
Correct |
5 ms |
36440 KB |
Output is correct |
5 |
Correct |
5 ms |
36184 KB |
Output is correct |
6 |
Correct |
5 ms |
36184 KB |
Output is correct |
7 |
Correct |
5 ms |
36340 KB |
Output is correct |
8 |
Correct |
5 ms |
36184 KB |
Output is correct |
9 |
Correct |
7 ms |
36184 KB |
Output is correct |
10 |
Correct |
7 ms |
36184 KB |
Output is correct |
11 |
Correct |
7 ms |
36188 KB |
Output is correct |
12 |
Correct |
13 ms |
36176 KB |
Output is correct |
13 |
Correct |
17 ms |
36184 KB |
Output is correct |
14 |
Correct |
8 ms |
36184 KB |
Output is correct |
15 |
Correct |
21 ms |
36268 KB |
Output is correct |
16 |
Correct |
6 ms |
36184 KB |
Output is correct |
17 |
Correct |
11 ms |
36184 KB |
Output is correct |
18 |
Correct |
43 ms |
36184 KB |
Output is correct |
19 |
Correct |
65 ms |
36276 KB |
Output is correct |
20 |
Correct |
77 ms |
36288 KB |
Output is correct |