【洛谷P2258】子矩阵

子矩阵

题目链接

搜索枚举选了哪几行，将DP降为一个一维的问题，

先预处理出w[i]表示该列上下元素差的绝对值之和

v[i][j]为第i列和第j列对应元素之差的绝对值之和

f[i][j]表示前j列中选i列，且最后一列为j的最小消耗

f[i][j]=min(f[i][j],f[i-1][j-k]+v[j-k][j]+w[j]);

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

#define reset(a) memset(a,0,sizeof(a))

#define _reset(a) memset(a,127,sizeof(a))

#define N 17

int n,m,r,c,a[N][N],ans=0x3f3f3f3f;

int f[N][N],w[N],v[N][N],path[N];

inline int read(){

    int x=; char c=getchar();

    while(c<''||c>'') c=getchar();

    while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }

    return x;

}

void dp(){

    reset(w); reset(v);

    _reset(f);

    for(int i=;i<=m;i++)

     for(int j=;j<=r;j++)

      w[i]+=abs(a[path[j]][i]-a[path[j-]][i]);

    for(int i=;i<m;i++)

     for(int j=i+;j<=m;j++)

      for(int k=;k<=r;k++)

       v[i][j]+=abs(a[path[k]][i]-a[path[k]][j]);

    f[][]=;

    for(int i=;i<=c;i++)

     for(int j=i;j<=m;j++)

      for(int k=;k<j;k++)

       f[i][j]=min(f[i][j],f[i-][k]+w[j]+v[k][j]);

    for(int i=c;i<=m;i++)

     ans=min(ans,f[c][i]);

}

void dfs(int t,int minn){

    if(t==r+){

        dp();

        return;

    }

    for(int i=minn;i<=n;i++){

        path[t]=i;

        dfs(t+,i+);

    }

}

int main()

{

    scanf("%d%d%d%d",&n,&m,&r,&c);

    for(int i=;i<=n;i++)

     for(int j=;j<=m;j++)

      a[i][j]=read();

    dfs(,);

    printf("%d\n",ans);

    return ;

}