%%%
by Masna_Kimoyo @ 2021-11-27 18:51:05
假如一个 1*8 的东西要切 9 刀你是不是一直会跑下去啊。
by w23c3c3 @ 2021-11-27 19:05:42
@[sycqwq](/user/151647) 就是楼上所说的问题，应该加个特判
tle的：
```cpp
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
using namespace std;
const int N=25,M=17,INF=0x3f3f3f3f;
int n,m=8;
int a[N][M],s[N][M],f[N][M][N][M][N-1],sum[N][N][N][N];
inline int read(){char cr=getchar();int x_=0,fui=1;while(cr<48){if(cr=='-')fui=-1;cr=getchar();}while(cr>47)x_=(x_*10)+(cr^48),cr=getchar();return x_*fui;}
inline int getsum(int x1,int yy1,int x2,int y2)
{
int sum=s[x2][y2]-s[x1-1][y2]-s[x2][yy1-1]+s[x1-1][yy1-1] ;
return sum*sum;
}
inline int dp(int x1,int yy1,int x2,int y2,int k)
{
//if((x2-x1)+(y2-yy1)<k) return f[x1][yy1][x2][y2][k]=INF;
if(k==0) return f[x1][yy1][x2][y2][k];
int dp1,dp2;
for(re int i=x1;i<x2;++i)
{
if(f[x1][yy1][i][y2][k-1]==INF)
{
f[x1][yy1][i][y2][k-1]=dp1=dp(x1,yy1,i,y2,k-1);
}
else dp1=f[x1][yy1][i][y2][k-1];
if(f[i+1][yy1][x2][y2][k-1]==INF)
{
f[i+1][yy1][x2][y2][k-1]=dp2=dp(i+1,yy1,x2,y2,k-1);
}
else dp2=f[i+1][yy1][x2][y2][k-1];
f[x1][yy1][x2][y2][k]=min(f[x1][yy1][x2][y2][k],min(dp1+sum[i+1][yy1][x2][y2],dp2+sum[x1][yy1][i][y2]));
}
for(re int i=yy1;i<y2;++i)
{
if(f[x1][yy1][x2][i][k-1]==INF)
{
f[x1][yy1][x2][i][k-1]=dp1=dp(x1,yy1,x2,i,k-1);
}
else dp1=f[x1][yy1][x2][i][k-1];
if(f[x1][i+1][x2][y2][k-1]==INF)
{
f[x1][i+1][x2][y2][k-1]=dp2=dp(x1,i+1,x2,y2,k-1);
}
else dp2=f[x1][i+1][x2][y2][k-1];
f[x1][yy1][x2][y2][k]=min(f[x1][yy1][x2][y2][k],min(dp1+sum[x1][i+1][x2][y2],dp2+sum[x1][yy1][x2][i]));
}
return f[x1][yy1][x2][y2][k];
}
signed main()
{
memset(f,INF,sizeof f);
//cout<<INF;
n=read();
for(re int i=1;i<=m;++i)
for(re int j=1;j<=m;++j)
a[i][j]=read();
for(re int i=1;i<=m;++i)
for(re int j=1;j<=m;++j)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
for(re int i=1;i<=m;++i)
for(re int j=1;j<=m;++j)
for(re int k=i;k<=m;++k)
for(re int p=j;p<=m;++p)
f[i][j][k][p][0]=sum[i][j][k][p]=getsum(i,j,k,p);
printf("%d",dp(1,1,m,m,n-1));
return 0;
}
```
ac的：
```cpp
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
using namespace std;
const int N=25,M=17,INF=0x3f3f3f3f;
int n,m=8;
int a[N][M],s[N][M],f[N][M][N][M][N-1],sum[N][N][N][N];
inline int read(){char cr=getchar();int x_=0,fui=1;while(cr<48){if(cr=='-')fui=-1;cr=getchar();}while(cr>47)x_=(x_*10)+(cr^48),cr=getchar();return x_*fui;}
inline int getsum(int x1,int yy1,int x2,int y2)
{
int sum=s[x2][y2]-s[x1-1][y2]-s[x2][yy1-1]+s[x1-1][yy1-1] ;
return sum*sum;
}
inline int dp(int x1,int yy1,int x2,int y2,int k)
{
if((x2-x1)+(y2-yy1)<k) return f[x1][yy1][x2][y2][k]=INF;
if(k==0) return f[x1][yy1][x2][y2][k];
int dp1,dp2;
for(re int i=x1;i<x2;++i)
{
if(f[x1][yy1][i][y2][k-1]==INF)
{
f[x1][yy1][i][y2][k-1]=dp1=dp(x1,yy1,i,y2,k-1);
}
else dp1=f[x1][yy1][i][y2][k-1];
if(f[i+1][yy1][x2][y2][k-1]==INF)
{
f[i+1][yy1][x2][y2][k-1]=dp2=dp(i+1,yy1,x2,y2,k-1);
}
else dp2=f[i+1][yy1][x2][y2][k-1];
f[x1][yy1][x2][y2][k]=min(f[x1][yy1][x2][y2][k],min(dp1+sum[i+1][yy1][x2][y2],dp2+sum[x1][yy1][i][y2]));
}
for(re int i=yy1;i<y2;++i)
{
if(f[x1][yy1][x2][i][k-1]==INF)
{
f[x1][yy1][x2][i][k-1]=dp1=dp(x1,yy1,x2,i,k-1);
}
else dp1=f[x1][yy1][x2][i][k-1];
if(f[x1][i+1][x2][y2][k-1]==INF)
{
f[x1][i+1][x2][y2][k-1]=dp2=dp(x1,i+1,x2,y2,k-1);
}
else dp2=f[x1][i+1][x2][y2][k-1];
f[x1][yy1][x2][y2][k]=min(f[x1][yy1][x2][y2][k],min(dp1+sum[x1][i+1][x2][y2],dp2+sum[x1][yy1][x2][i]));
}
return f[x1][yy1][x2][y2][k];
}
signed main()
{
memset(f,INF,sizeof f);
//cout<<INF;
n=read();
for(re int i=1;i<=m;++i)
for(re int j=1;j<=m;++j)
a[i][j]=read();
for(re int i=1;i<=m;++i)
for(re int j=1;j<=m;++j)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
for(re int i=1;i<=m;++i)
for(re int j=1;j<=m;++j)
for(re int k=i;k<=m;++k)
for(re int p=j;p<=m;++p)
f[i][j][k][p][0]=sum[i][j][k][p]=getsum(i,j,k,p);
printf("%d",dp(1,1,m,m,n-1));
return 0;
}
```
by Watanabe @ 2022-12-29 11:34:56