然后这是一道非常暴力的题，首先是直接dfs的暴力操作：
因为同时枚举行和列不好枚举，所以我们可以先枚举行，当行枚举完了，再枚举列。然后都枚举完了，就可以按照题目要求算一下，然后比较算到的答案与当前值的大小，保留较小的那一个。
CODE：
#include<bits/stdc++.h>
using namespace std;
int n,m,r,c,ans=0x7ffffff;
int Map[17][17],dp2[17],dp1[17];
void dp(){
int now = 0;
for (int i=1;i<=r;i++)
for (int j=2;j<=c;j++)
now+=abs(Map[dp1[i]][dp2[j]]-Map[dp1[i]][dp2[j-1]]);
for (int i=2;i<=r;i++)
for (int j=1;j<=c;j++)
now+=abs(Map[dp1[i]][dp2[j]]-Map[dp1[i-1]][dp2[j]]);
ans=min(ans,now);
}
void dfs(int x,int y,int nr,int nc){
if(nc==c+1){
dp();
return;
}
if(nr==r+1){//当已经枚举了r条边
for(int i=y;i<=m;i++){
dp2[nc]=i;
dfs(x,i+1,nr,nc+1);
}
return;
}
else
for(int i=x;i<=n;i++){
dp1[nr]=i;
dfs(i+1,y,nr+1,nc);
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&r,&c);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&Map[i][j]);
dfs(1,1,1,1);
cout<<ans<<endl;
return 0;
}
亲测不加-o2 55pts，加了-o2 70pts；
然后是正解。
#define ych 预处理
正解也是很神奇的，他不是一个简单地DP，而是建立在搜索上的DP！？
首先我们还是搜索，这次只搜索行，然后当搜索了r行之后，对列进行dp。
搜索：
void dfs(int x,int nr){
if(nr==r+1) return dp();
if(x==n+1) return;
for(int i=x;i<=n;i++){
dp1[nr]=i;
dfs(i+1,nr+1);
}
}
dp1[i]记录枚举的边的编号；
x记录当前已经枚举到的边，nr记录选择了几条边；
首先几个定义的数组：
ver[i]，定义的前提是你已经枚举好行了（分别记为k1，k2，……，kr），然后表示的是：第i列的枚举的每相邻的两行的差的绝对值的和。
emm
有点乱，然后我们举个例子：
假设我们枚举的行是：k1，k2，k3……kr，然后我们用Map[i][j]存第i行第j列的值；
然后ver[i]=abs(Map[k2][i]-Map[k1][i])+abs(Map[k3][i]-Map[k2][i])+……+abs(Map[kr][i]-Map[kr-1][i])
对应到代码里就是：
for(int i=1;i<=m;i++)
for(int j=2;j<=r;j++)
ver[i]+=abs(Map[dp1[j]][i]-Map[dp1[j-1]][i]);
del[i][k]，定义前提与ver相同，然后表示的是：第i列和第k列左右差的和，然后还是很抽象对吧：
再举个例子：
假设我们枚举的行是：k1，k2，k3……kr，然后我们用Map[i][j]存第i行第j列的值；
然后del[i][k]=abs(Map[k1][i]-Map[k1][k])+abs(Map[k2][i]-Map[k2][k])+……+abs(Map[kr][i]-Map[kr][k]);
对应到代码里：
for(int i=1;i<=m;i++)//枚举是哪一列
for(int k=i+1;k<=m;k++)//枚举另一列
for(int j=1;j<=r;j++)//枚举行
del[i][k]+=abs(Map[dp1[j]][k]-Map[dp1[j]][i]);
然后是ych：
对于只选一列的情况，显然它的值就等于所选那一列的ver（没有左右可以减所以莫得del的事情）；
for(int i=1;i<=m;i++)
f[i][1]=ver[i];
然后是DP正解部分：
定义f[i][j]表示在前i条边中选择j条边并且恰好选择了第i条边的最小分值（哦对了别忘记初始化f为一个很大的数），那么转移方程就是：f[i][j]=min(f[i][j],f[i-k][j-1]+ver[i]+del[i-k][i]);
大概是可以理解的吧？解释一下：
f[i-k][j-1]+ver[i]+del[i-k][i]：从第i-k列选择j-1条边，然后再选择第i条边（选择以后与i相邻的就是i-k这一列，那么需要加的代价就是第i列的ver，以及第i列和第i-k列的del）；
然后代码实现：
for(int i=1;i<=m;i++)
for(int j=1;j<=c;j++)
for(int k=1;k<i&&i-k>=j-1;k++)
f[i][j]=min(f[i][j], f[i-k][j-1]+ver[i]+del[i-k][i]);
这里的k要保证i-k≥j-1，原因是f[i-k][j-1]表示的是从前i-k列中选择j-1列，如果i-k<j-1了，那显然选不了，因此直接不必选择了；
最后枚举最小的：
for(int i=c;i<=m;i++)//从c开始枚举也是因为楼上i-k与j-1的关系的原因
ans=min(ans,f[i][c]);
CODE：
#include<bits/stdc++.h>
using namespace std;
int n,m,r,c,ans=0x7ffffff;
int Map[17][17],dp1[17],ver[17],del[17][17],f[17][17];
void dp(){
memset(f,63,sizeof(f));
memset(ver,0,sizeof(ver));
memset(del,0,sizeof(del));
for(int i=1;i<=m;i++)
for(int j=2;j<=r;j++)
ver[i]+=abs(Map[dp1[j]][i]-Map[dp1[j-1]][i]);
for(int i=1;i<=m;i++)
for(int k=i+1;k<=m;k++)
for(int j=1;j<=r;j++)
del[i][k]+=abs(Map[dp1[j]][k]-Map[dp1[j]][i]);
for(int i=1;i<=m;i++)//something call 初始化
f[i][1]=ver[i];
for(int i=1;i<=m;i++)
for(int j=1;j<=c;j++)
for(int k=1;k<i&&i-k>=j-1;k++)
f[i][j] = min(f[i][j], f[i - k][j - 1] + ver[i] + del[i - k][i]);
for(int i=c;i<=m;i++)
ans=min(ans,f[i][c]);
}
void dfs(int x,int nr){
if(nr==r+1) return dp();
if(x==n+1) return;
for(int i=x;i<=n;i++){
dp1[nr]=i;
dfs(i+1,nr+1);
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&r,&c);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&Map[i][j]);
dfs(1,1);
cout<<ans<<endl;
return 0;
}
end-