#include <bits/stdc++.h>
using namespace std;
int a[55][55], b[55][55], dp[55][55][55][55];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
{
cin >> a[i][j];
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
}
}
for (int id=0; id<n; id++)
{
for (int il=1; il<=n-id; il++)
{
int ir=il+id;
for (int jd=0; jd<m; jd++)
{
for (int jl=1; jl<=m-jd; jl++)
{
int jr=jl+jd;
if (il==ir && jl==jr)
continue;
dp[il][ir][jl][jr]=1e9;
for (int i=il; i<ir; i++)
dp[il][ir][jl][jr]=min(dp[il][ir][jl][jr], dp[il][i][jl][jr]+dp[i+1][ir][jl][jr]);
for (int j=jl; j<jr; j++)
dp[il][ir][jl][jr]=min(dp[il][ir][jl][jr], dp[il][ir][jl][j]+dp[il][ir][j+1][jr]);
dp[il][ir][jl][jr]+=b[ir][jr]-b[ir][jl-1]-b[il-1][jr]+b[il-1][jl-1];
}
}
}
}
cout << dp[1][n][1][m];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |