#include <bits/stdc++.h>
using namespace std;
const int mn=55;
int a[mn][mn];
int dp[mn][mn][mn][mn];
int pref[mn][mn];
const int INF=1e9;
int prefiksnaoo(int i,int j,int x,int y)
{
int prefiksna=0;
if(i==0 && j==0) prefiksna=pref[x][y];
else if(i==0) prefiksna=pref[x][y]-pref[x][j-1];
else if(j==0) prefiksna=pref[x][y]-pref[i-1][y];
else prefiksna=pref[x][y]+pref[i-1][j-1]-pref[x][j-1]-pref[i-1][y];
return prefiksna;
}
int resi(int i,int j,int x,int y)
{
if(dp[i][j][x][y]!=-1) return dp[i][j][x][y];
int mn=INF;
int prefiksna=prefiksnaoo(i,j,x,y);
for(int k=j;k<y;k++)
{
//mn=min(mn,dp[i][j][x][k]+dp[i][k+1][x][y]+prefiksna);
mn=min(mn,resi(i,j,x,k)+resi(i,k+1,x,y)+prefiksna);
}
for(int k=i;k<x;k++)
{
//mn=min(mn,dp[i][j][k][y]+dp[k+1][j][x][y]+prefiksna);
mn=min(mn,resi(i,j,k,y)+resi(k+1,j,x,y)+prefiksna);
}
return dp[i][j][x][y]=mn;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<mn;i++)
for(int j=0;j<mn;j++)
for(int i1=0;i1<mn;i1++)
for(int j1=0;j1<mn;j1++) dp[i][j][i1][j1]=-1;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
dp[i][j][i][j]=0;
}
}
pref[0][0]=a[0][0];
for(int i=1;i<n;i++) pref[i][0]=pref[i-1][0]+a[i][0];
for(int j=1;j<m;j++) pref[0][j]=pref[0][j-1]+a[0][j];
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++) pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
}
//cout<<pref[1][1]<<endl;
//cout<<prefiksnaoo(0,1,1,1)<<endl;
//cout<<prefiksnaoo(1,1,1,2)<<endl;
cout<<resi(0,0,n-1,m-1);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
36044 KB |
Output is correct |
2 |
Correct |
18 ms |
36044 KB |
Output is correct |
3 |
Correct |
17 ms |
36044 KB |
Output is correct |
4 |
Correct |
17 ms |
36084 KB |
Output is correct |
5 |
Correct |
17 ms |
36052 KB |
Output is correct |
6 |
Correct |
17 ms |
36020 KB |
Output is correct |
7 |
Correct |
17 ms |
36116 KB |
Output is correct |
8 |
Correct |
21 ms |
36008 KB |
Output is correct |
9 |
Correct |
22 ms |
36044 KB |
Output is correct |
10 |
Correct |
24 ms |
36044 KB |
Output is correct |
11 |
Correct |
23 ms |
36084 KB |
Output is correct |
12 |
Correct |
43 ms |
36120 KB |
Output is correct |
13 |
Correct |
61 ms |
36120 KB |
Output is correct |
14 |
Correct |
27 ms |
36004 KB |
Output is correct |
15 |
Correct |
71 ms |
36024 KB |
Output is correct |
16 |
Correct |
20 ms |
36132 KB |
Output is correct |
17 |
Correct |
36 ms |
36088 KB |
Output is correct |
18 |
Correct |
171 ms |
36156 KB |
Output is correct |
19 |
Correct |
277 ms |
36128 KB |
Output is correct |
20 |
Correct |
334 ms |
36132 KB |
Output is correct |