先枚举行再DP列。好题，详见代码

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 using namespace std; 8 const int N=20; 9 const int inf =0x3f3f3f3f;10 int n,m,r,c,p[N][N],v[N],f[N],res=inf,t[N],t1[N][N];11 12 int DP() {13 memset(t,0,sizeof t);14 memset(t1,0,sizeof t1);15 for (int i=1; i<=m; i++)//预处理同一列相邻行之间的差值16 for (int j=1; j
            
             =i; j--) {23 f[j]=inf;24 for (int k=j-1; k>=i-1; k--) f[j]=min(f[j],f[k]+t1[k][j]);25 f[j]+=t[j];26 }27 int ans=inf;28 for (int i=c; i<=m; i++) ans=min(ans,f[i]);29 return ans;30 }31 32 void DFS(int i,int dep) { //枚举行数33 if (dep==r) {34 res=min(res,DP());35 return;36 }37 for (int j=i; j<=n-r+dep+1; j++) {38 v[++v[0]]=j;39 DFS(j+1,dep+1);40 v[v[0]--]=0;41 }42 }43 44 void work() {45 DFS(1,0);46 printf("%d\n",res);47 }48 49 int main() {50 memset(v,0,sizeof(v));51 scanf("%d%d%d%d",&n,&m,&r,&c);52 for (int i=1; i<=n; i++)53 for (int j=1; j<=m; j++)54 scanf("%d",&p[i][j]);55 work();56 return 0;57 }