P2258 子矩阵

本题如果想纯的话。。简直难以名状。

解决方法就是不要只想着，放宽一点复杂度，

想想能不能通过少量的枚举来使更加好写。

这一题，就是枚举行或者列，复杂度,可以接受。

那么行确定了，列的就十分好想了。

#include<iostream>
#include<memory.h>
#define maxn 20
#define sx 20000000
#define miin(a,b) ((a)<(b)?(a):(b))
#define abss(a,b) ((a)<(b)?((b)-(a)):((a)-(b)))
using namespace std;

int n,m,a,b,Ans=sx,z[maxn][maxn],s[maxn][maxn],dp[maxn][maxn],hs[maxn],csh[maxn];
void cl(){
    for(int i=1;i<=n;i++)
    memset(s[i],0,sizeof(s[i]));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    dp[i][j]=sx;
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
    for(int k=1;k<=b;k++)
    s[i][j]+=abss(z[i][csh[k]],z[j][csh[k]]);
    memset(hs,0,sizeof(hs));
    for(int i=1;i<=n;i++)
    for(int j=1;j<b;j++)
    hs[i]+=abss(z[i][csh[j]],z[i][csh[j+1]]);
    for(int i=1;i<=n;i++)dp[i][1]=hs[i];
    for(int i=2;i<=n;i++)
    for(int k=2;k<=a&&k<=i;k++)
    for(int j=k-1;j<i;j++)
    dp[i][k]=miin(dp[i][k],dp[j][k-1]+hs[i]+s[j][i]);
    /*因为前面为了省复杂度只初始化了一半，
    然后这里之前写成s[i][j]导致bug一直
    算不进去列和。。*/
    for(int i=a;i<=n;i++)
    Ans=miin(Ans,dp[i][a]);
}
void dfs(int e,int re){
    if(e==b){
        cl();
        return;
    }
    for(int i=re+1;i<=m;i++){
        csh[e+1]=i;
        dfs(e+1,i);
    }
}
int main(){
    cin>>n>>m>>a>>b;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {cin>>z[i][j];}
    dfs(0,0);
    cout<<Ans;
    return 0;
}