题目
思路
暴力枚举每一列情况,然后设
f
x
,
y
f_{x,y}
fx,y为前y行选x个的最优解,
d
x
d_x
dx为x列所需代价
e
x
,
y
e_{x,y}
ex,y为x,y2行相邻的代价,则有:
f
i
,
j
=
m
i
n
(
f
i
−
1
,
k
+
d
j
+
e
k
,
j
)
(
1
<
=
i
<
=
c
,
i
<
=
j
<
=
m
,
0
<
=
k
<
j
)
f_{i,j}=min(f_{i-1,k}+d_j+e_{k,j})(1<=i<=c,i<=j<=m,\color{red}{0<=k<j})
fi,j=min(fi−1,k+dj+ek,j)(1<=i<=c,i<=j<=m,0<=k<j)
code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,r,c,a[20][20],b[20],d[20][20],e[20][20],f[20],ans=1<<30;
void dp()
{
memset(b,0,sizeof(b));
memset(e,0,sizeof(e));
memset(d,127,sizeof(d));
for (int i=1;i<=m;i++) for (int j=1;j<r;j++) b[i]+=abs(a[f[j]][i]-a[f[j+1]][i]);
for (int i=1;i<=m;i++) for (int j=i+1;j<=m;j++) for (int k=1;k<=r;k++) e[i][j]+=abs(a[f[k]][i]-a[f[k]][j]);
d[0][0]=0;
for (int i=1;i<=c;i++)
{
for (int j=i;j<=m;j++)
{
for (int k=0;k<j;k++) d[i][j]=min(d[i][j],d[i-1][k]+b[j]+e[k][j]);
if (i==c) ans=min(ans,d[c][j]);
}
}
return;
}
void dfs(int x,int y)
{
if (y>r)
{
dp();
return;
}
if (x>n) return;
dfs(x+1,y);
f[y]=x;
dfs(x+1,y+1);
return;
}
signed main()
{
cin>>n>>m>>r>>c;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cin>>a[i][j];
dfs(1,1);
cout<<ans;
return 0;
}