题解 P2258 【子矩阵】

· · 题解

本人太弱，不会DP，于是就有了这个只用DFS的题解

首先，我们会想到暴力做法，时间复杂度约为O(C(n,r)C(m,c)rc)，可以得到60分，代码就不提供了

暴力做法之所以慢，是因为进行了重复的计算，而且缺少剪枝。

矩阵的分值包含两部分，一是同一行两个数差的绝对值，二是同一列两个数差的绝对值。如果我们先搜索行再搜索列，第二种分值就可以在搜索行时计算，而第一种分值在搜索列时边搜索边计算。

我们还可以加上搜索常用的最优性剪枝，就是当此时矩阵的分值已经大于等于当前最优答案，那么就退出搜索

代码如下：

void dfsl(ci&x,ci&y,ci&z){//const类型传参，卡常数必备，x为上一列，y为已搜索的列数，z为当前答案
    if(y==c){
        s=z;//更新答案
        return;
    }
    register int i=x+1,en=y+m-c+2,j,zz;//register类型卡常数，en为搜索终止位置
    for(;i<en;++i){
        zz=z+p[i];//p数组存储第二种分值
        if(zz>=s)continue;//剪枝
        if(x!=0){
            for(j=0;j<r;++j){
                zz+=abs(v[e[j]][i]-v[e[j]][x]);//累加第一种分值
            }
        }
        if(zz<s)dfsl(i,y+1,zz);
    }
}
void dfsh(ci&x,ci&y){//搜索行
    if(y==r){
        dfsl(0,0,0);//搜完则搜索列
        return;
    }
    register int i=x+1,en=y+n-r+2,j,q[19];//q数组必须在dfsh函数内定义，用于回溯
    for(;i<en;++i){
        if(x!=0){
            for(j=1;j<=m;++j){
                q[j]=abs(v[x][j]-v[i][j]),p[j]+=q[j];
            }
        }
        e[y]=i,dfsh(i,y+1);//e数组保存取出的行
        if(x!=0){
            for(j=1;j<=m;++j)p[j]-=q[j];//回溯
        }
    }
}

80分，超时，需要继续优化

我们会发现abs进行调用的次数很多，因此可以预处理所有分值，减少重复计算

代码如下：

for(i=1;i<n;++i){//预处理第二种分值
        for(j=i+1;j<=n;++j){
            for(k=1;k<=m;++k){
                g[i][j][k]=abs(v[i][k]-v[j][k]);
            }
        }
    }
    for(i=1;i<m;++i){//预处理第一种分值
        for(j=i+1;j<=m;++j){
            for(k=1;k<=n;++k){
                h[i][j][k]=abs(v[k][i]-v[k][j]);
            }
        }
    }

同时相应修改DFS函数：

void dfsl(ci&x,ci&y,ci&z){
    if(y==c){
        s=z;
        return;
    }
    register int i=x+1,en=y+m-c+2,j,zz;
    for(;i<en;++i){
        zz=z+p[i];
        if(zz>=s)continue;
        if(x!=0){
            for(j=0;j<r;++j){
                zz+=h[x][i][e[j]];//累加第一种分值
            }
        }
        if(zz<s)dfsl(i,y+1,zz);
    }
}
void dfsh(ci&x,ci&y){
    if(y==r){
        dfsl(0,0,0);
        return;
    }
    register int i=x+1,en=y+n-r+2,j;
    for(;i<en;++i){
        if(x!=0){
            for(j=1;j<=m;++j){
                p[j]+=g[x][i][j];//第二种分值
            }
        }
        e[y]=i,dfsh(i,y+1);
        if(x!=0){
            for(j=1;j<=m;++j)p[j]-=g[x][i][j];//回溯
        }
    }
}

依然是80分，但是速度相比之前略快，需要继续剪枝

我们可以考虑将累加第一种分值在dfsh函数中进行，因为dfsh调用次数少于dfsl，因此可以减少重复计算

代码如下：

void dfsl(ci&x,ci&y,ci&z){
    if(y==c){
        s=z;
        return;
    }
    register int i=x+1,en=y+m-c+2,j,zz;
    for(;i<en;++i){
        zz=z+p[i]+w[x][i];//可以一次性求出两种分值之和
        if(zz<s)dfsl(i,y+1,zz);
    }
}
void dfsh(ci&x,ci&y){
    if(y==r){
        dfsl(0,0,0);
        return;
    }
    register int i=x+1,en=y+n-r+2,j,k;
    for(;i<en;++i){
        if(x!=0){
            for(j=1;j<=m;++j){
                p[j]+=g[x][i][j];
            }
        }
        for(j=1;j<m;++j){
            for(k=j+1;k<=m;++k){
                w[j][k]+=h[j][k][i];//用w数组保存第一种分值
            }
        }
        e[y]=i,dfsh(i,y+1);
        if(x!=0){
            for(j=1;j<=m;++j)p[j]-=g[x][i][j];
        }
        for(j=1;j<m;++j){
            for(k=j+1;k<=m;++k){
                w[j][k]-=h[j][k][i];//注意w数组也要回溯
            }
        }
    }
}

这样就可以得到100分了