luogu 2258 子矩阵

S1

说实话，这道题已经做了很久了。最开始的思路是想要直接DP，想过四维的但是被证伪了，状压的话一定会MLE，就暂时搁置了。

S2

今天重新捡起来这道题，第一个想到的算法就是DFS。但是如果搜行然后搜列的话就特别暴力，完全没有优化的思路。

S3

看题解
其实仔细思考的话应该能想出来。
正确的方法应该是先用DFS搜行的全组合，之后再用DP，f[i][j]表示选i列，最后一列是j的时候的最小值。因为数据实在是小，这个完全可以实现。
想到了状态转移方程f[i][j]=min(f[i][j],f[i-1][k]+l[j]+s[k][j]);
那么DP反而不是难点，难点在于DFS，这个时间复杂度有点看脸，试着写写看。
一遍过了，但是过程并不轻松，犯了两个错误。
1.l[i]没有在每一个组合都更新。l[i]是选好的行上面第i列的分值之和，而不是总的。
2.在状态转移的时候，对于每一个f[i][j]都用了f[i-1][0]来推，因为f[i][0]=l[i]，但除了第1列之外并不能用第0列来推，以后状态转移的时候一定要注意这一点，一定要单独考虑考虑第0行或者第0列。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define rint register int
#define inv inline void
#define big 1e9
using namespace std;
int s[21][21],f[21][21],l[21],q[21],a[21][21],n,m,ans,r,c;
inv dp()
{
    for (rint i=1;i<=m;i++)
    {
        l[i]=0; 
        for (rint j=2;j<=r;j++)
            l[i]+=abs(a[q[j]][i]-a[q[j-1]][i]);
    }
    for (rint i=1;i<=m-1;i++)
        for (rint j=i+1;j<=m;j++)
        {
            s[i][j]=0;
            for (rint k=1;k<=r;k++)
                s[i][j]+=abs(a[q[k]][i]-a[q[k]][j]);
        }
    for (rint i=1;i<=c;i++)
        for (rint j=1;j<=m;j++)
            f[i][j]=big;
    for (rint i=1;i<=c;i++)
        for (rint j=i;j<=m;j++)
            for (rint k=i-1;k<=j-1;k++)
                f[i][j]=min(f[i][j],f[i-1][k]+l[j]+s[k][j]);
    for (rint i=1;i<=m;i++)
        ans=min(ans,f[c][i]); 
}
inv dfs(int x,int dep)
{	
    q[dep]=x;
    if (dep==r)
    {
        dp();
        return; 
    }
    for (rint i=x+1;i<=n-r+dep+1;i++) dfs(i,dep+1);
    q[dep]=0;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&r,&c);
    for (rint i=1;i<=n;i++)
        for (rint j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    ans=big;
    for (rint i=1;i<=n-r+1;i++)
        dfs(i,1);
    printf("%d",ans);
}

总结：

一个算法想了一很久想不出来，有可能是自己的能力到了极限，也有可能是根本就不用这个算法，试着开辟一下新路。
在没有办法的时候，大胆的尝试DFS，只要剪枝剪得好不是没有可能AC
DFS和DP都不是很精通，一定要多做题把题感练回来。
以后状态转移的时候一定要注意单独考虑考虑第0行或者第0列。