【洛谷p2258】子矩阵

子矩阵【题目链接】

然后这是一道非常暴力的题,首先是直接dfs的暴力操作:

因为同时枚举行和列不好枚举,所以我们可以先枚举行,当行枚举完了,再枚举列。然后都枚举完了,就可以按照题目要求算一下,然后比较算到的答案与当前值的大小,保留较小的那一个。

CODE:

#include<bits/stdc++.h>

using namespace std;

int n,m,r,c,ans=0x7ffffff;
int Map[17][17],dp2[17],dp1[17];

void dp(){
    int now = 0;
    for (int i=1;i<=r;i++)
        for (int j=2;j<=c;j++)
            now+=abs(Map[dp1[i]][dp2[j]]-Map[dp1[i]][dp2[j-1]]);
    for (int i=2;i<=r;i++)
        for (int j=1;j<=c;j++)
            now+=abs(Map[dp1[i]][dp2[j]]-Map[dp1[i-1]][dp2[j]]);
    ans=min(ans,now);
}

void dfs(int x,int y,int nr,int nc){
    if(nc==c+1){
        dp();
        return;
    }
    if(nr==r+1){//当已经枚举了r条边
        for(int i=y;i<=m;i++){
            dp2[nc]=i;
            dfs(x,i+1,nr,nc+1);
        }
        return;
    }
    else 
        for(int i=x;i<=n;i++){
            dp1[nr]=i;
            dfs(i+1,y,nr+1,nc);
        }
}

int main(){
    scanf("%d%d%d%d",&n,&m,&r,&c);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&Map[i][j]);
    dfs(1,1,1,1);
    cout<<ans<<endl;
    return 0;
}

亲测不加-o2 55pts,加了-o2 70pts;

然后是正解。

#define ych 预处理

正解也是很神奇的,他不是一个简单地DP,而是建立在搜索上的DP!?

首先我们还是搜索,这次只搜索行,然后当搜索了r行之后,对列进行dp。

搜索:

void dfs(int x,int nr){
    if(nr==r+1) return dp();
    if(x==n+1) return;
        for(int i=x;i<=n;i++){
            dp1[nr]=i;
            dfs(i+1,nr+1);
        }
}

dp1[i]记录枚举的边的编号;

x记录当前已经枚举到的边,nr记录选择了几条边;

首先几个定义的数组:

ver[i],定义的前提是你已经枚举好行了(分别记为k1,k2,……,kr),然后表示的是:第i列的枚举的每相邻的两行的差的绝对值的和。

emm

有点乱,然后我们举个例子:

 假设我们枚举的行是:k1,k2,k3……kr,然后我们用Map[i][j]存第i行第j列的值;

然后ver[i]=abs(Map[k2][i]-Map[k1][i])+abs(Map[k3][i]-Map[k2][i])+……+abs(Map[kr][i]-Map[kr-1][i])

对应到代码里就是:

for(int i=1;i<=m;i++)
        for(int j=2;j<=r;j++)
            ver[i]+=abs(Map[dp1[j]][i]-Map[dp1[j-1]][i]);

del[i][k],定义前提与ver相同,然后表示的是:第i列和第k列左右差的和,然后还是很抽象对吧:

再举个例子:

 假设我们枚举的行是:k1,k2,k3……kr,然后我们用Map[i][j]存第i行第j列的值;

然后del[i][k]=abs(Map[k1][i]-Map[k1][k])+abs(Map[k2][i]-Map[k2][k])+……+abs(Map[kr][i]-Map[kr][k]);

对应到代码里:

for(int i=1;i<=m;i++)//枚举是哪一列
        for(int k=i+1;k<=m;k++)//枚举另一列
            for(int j=1;j<=r;j++)//枚举行
                del[i][k]+=abs(Map[dp1[j]][k]-Map[dp1[j]][i]);

然后是ych:

对于只选一列的情况,显然它的值就等于所选那一列的ver(没有左右可以减所以莫得del的事情);

 for(int i=1;i<=m;i++)
        f[i][1]=ver[i];

然后是DP正解部分:

定义f[i][j]表示在前i条边中选择j条边并且恰好选择了第i条边的最小分值(哦对了别忘记初始化f为一个很大的数),那么转移方程就是:f[i][j]=min(f[i][j],f[i-k][j-1]+ver[i]+del[i-k][i]);

大概是可以理解的吧?解释一下:

f[i-k][j-1]+ver[i]+del[i-k][i]:从第i-k列选择j-1条边,然后再选择第i条边(选择以后与i相邻的就是i-k这一列,那么需要加的代价就是第i列的ver,以及第i列和第i-k列的del);

然后代码实现:

for(int i=1;i<=m;i++)
        for(int j=1;j<=c;j++)
            for(int k=1;k<i&&i-k>=j-1;k++)
                f[i][j]=min(f[i][j], f[i-k][j-1]+ver[i]+del[i-k][i]);

这里的k要保证i-k≥j-1,原因是f[i-k][j-1]表示的是从前i-k列中选择j-1列,如果i-k<j-1了,那显然选不了,因此直接不必选择了;

最后枚举最小的:

for(int i=c;i<=m;i++)//从c开始枚举也是因为楼上i-k与j-1的关系的原因
        ans=min(ans,f[i][c]);

CODE:

#include<bits/stdc++.h>
using namespace std;

int n,m,r,c,ans=0x7ffffff;
int Map[17][17],dp1[17],ver[17],del[17][17],f[17][17];

void dp(){
    memset(f,63,sizeof(f));
    memset(ver,0,sizeof(ver));
    memset(del,0,sizeof(del));
    for(int i=1;i<=m;i++)
        for(int j=2;j<=r;j++)
            ver[i]+=abs(Map[dp1[j]][i]-Map[dp1[j-1]][i]);
    for(int i=1;i<=m;i++)
        for(int k=i+1;k<=m;k++)
            for(int j=1;j<=r;j++)
                del[i][k]+=abs(Map[dp1[j]][k]-Map[dp1[j]][i]);
    for(int i=1;i<=m;i++)//something call 初始化 
        f[i][1]=ver[i];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=c;j++)
            for(int k=1;k<i&&i-k>=j-1;k++)
                f[i][j] = min(f[i][j], f[i - k][j - 1] + ver[i] + del[i - k][i]);
    for(int i=c;i<=m;i++)
        ans=min(ans,f[i][c]);
}

void dfs(int x,int nr){
    if(nr==r+1) return dp();
    if(x==n+1) return;
        for(int i=x;i<=n;i++){
            dp1[nr]=i;
            dfs(i+1,nr+1);
        }
}

int main(){
    scanf("%d%d%d%d",&n,&m,&r,&c);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&Map[i][j]);
    dfs(1,1);
    cout<<ans<<endl;
    return 0;
}

end-

上一篇:[线段树]HDU-1754板子题入门ver


下一篇:在阿里云服务器(ECS)上从零开始搭建nginx服务器