P2258

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,r,c,a[100][100],dp[100][100][100],b[100][100],ans=LONG_LONG_MAX;
ll x[100][100],y[100];
int vis[100],tot;
void solve(){
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    for(ll i=1;i<=m;i++){
        for(ll j=2;j<=r;j++){
            y[i]+=abs(a[vis[j]][i]-a[vis[j-1]][i]);
        }
    }
    for(ll i=1;i<m;i++){
        for(ll j=i+1;j<=m;j++){
            for(ll k=1;k<=r;k++){
                x[i][j]+=abs(a[vis[k]][i]-a[vis[k]][j]);
            }
        }
    }
    memset(dp,127,sizeof(dp));
    for(int i=0;i<=m;i++)dp[i][0][0]=0;
    for(ll i=1;i<=m;i++){//前i列
        for(ll j=1;j<=min(i,c);j++){//选了j列
            for(ll k=j-1;k<i;k++){//最后一列
                dp[i][j][i]=min(dp[i][j][i],dp[i-1][j-1][k]+x[k][i]+y[i]);
                if(k>=j && i-1>=j)dp[i][j][k]=dp[i-1][j][k];
            }
        }
    }
    for(ll i=c;i<=m;i++)ans=min(ans,dp[m][c][i]);
}
void dfs(ll k,ll cnt){
    if(k>n){
        if(cnt==r)solve();
        return;
    }if(cnt<r){
        vis[cnt+1]=k;
        dfs(k+1,cnt+1);
    }
    dfs(k+1,cnt);
}
int 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,0);
    cout<<ans<<endl;
    return 0;
}

70TLE求助各位万能谷民