#include <bits/stdc++.h>
#define MAX 53
using namespace std;
int sp[MAX][MAX];
int dp[MAX][MAX][MAX][MAX];
int N,M;
void read()
{
cin>>N>>M;
int i,j;
for(i=1;i<=N;++i)
for(j=1;j<=M;++j)
cin>>sp[i][j];
}
void precalc()
{
int i,j;
for(i=1;i<=N;++i)
for(j=1;j<=M;++j)
sp[i][j]+=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1];
}
int dpr(int l1,int c1,int l2,int c2)
{
if(l1==l2 && c1==c2)
return 0;
if(dp[l1][c1][l2][c2])
return dp[l1][c1][l2][c2];
int i;
dp[l1][c1][l2][c2]=1e9;
for(i=l1;i<l2;++i)
dp[l1][c1][l2][c2]=min(dp[l1][c1][l2][c2],dpr(l1,c1,i,c2)+dpr(i+1,c1,l2,c2));
for(i=c1;i<c2;++i)
dp[l1][c1][l2][c2]=min(dp[l1][c1][l2][c2],dpr(l1,c1,l2,i)+dpr(l1,i+1,l2,c2));
dp[l1][c1][l2][c2]+=sp[l2][c2]-sp[l2][c1-1]-sp[l1-1][c2]+sp[l1-1][c1-1];
return dp[l1][c1][l2][c2];
}
void write()
{
cout<<dpr(1,1,N,M);
}
int main()
{
read();
precalc();
write();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |