[洛谷P2258][NOIP2014PJ]子矩阵(dfs)(dp)

NOIP 2014普及组 T4(话说一道PJ组的题就把我卡了一个多小时诶)

这道题在我看第一次的时候是没有意识到这是一道DP题的，然后就摁着DFS敲了好长时间，结果敲了一个TLE

这是DP!!!

下面开始进入正题

题目描述

给出如下定义：

子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵（保持行与列的相对顺序）被称为原矩阵的一个子矩阵。

例如，下面左图中选取第22、44行和第22、44、55列交叉位置的元素得到一个2 \times 32×3的子矩阵如右图所示。

9 3 3 3 9

9 4 8 7 4

1 7 4 6 6

6 8 5 6 9

7 4 5 6 1

的其中一个2 \times 32×3的子矩阵是

4 7 4

8 6 9

相邻的元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。
矩阵的分值：矩阵中每一对相邻元素之差的绝对值之和。

本题任务：给定一个nn行mm列的正整数矩阵，请你从这个矩阵中选出一个rr行cc列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。

输入输出格式

输入格式：

第一行包含用空格隔开的四个整数n,m,r,cn,m,r,c，意义如问题描述中所述，每两个整数之间用一个空格隔开。

接下来的nn行，每行包含mm个用空格隔开的整数，用来表示问题描述中那个nn行mm列的矩阵。

输出格式：

一个整数，表示满足题目描述的子矩阵的最小分值。

样例：
输入

输出

这道题就是将题目所给你的矩阵进行“选取”行与列的操作，从而得到所求的最大值的集合，但是重要的是我们不知道题目所给的行和列的值是多少，因此我们可以对此进行一个循环中的判断操作，在选出来这个行之后再去考虑列的情况，从而得出最优决策。

这个地方还有一个降维操作，就是我们在一个r * m(事先以及决定了选取那几行，该去考虑列的问题时)的矩阵中选取c列，这个时候我们可以把二维降低到一维，(因为这其中行已经有了判断的标准，我们只需要进行列的操作就足够了).

下面开始讲DP过程：

我们设f[i][j]表示在这个r*m的矩阵中，在其前i列中选择j列（且选的列中包括第i列），组成的子矩阵中，最小值（即其相邻元素的差的绝对值的和的最小值（之后的值等表达也是指的这个东西，即题目要求求出的值））是多少。

这样，推出状态转移方程如下：

f[i][j] = min (f[k][j-1] + hc[i][k] + lc[i])

下面就都是一些细节上的优化，代码里面已经讲的很清楚了。

Code:

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int n,m,r,c,gs=,minn=0x7fffffff,cmin;  //不可能选取0列

int a[][];

int ch[],hc[][],lc[];  //hc[i][j] 对于第i列与第j列之间，所有同一行元素的差的绝对值的和

                               //lc[i]指的是第i列中所有元素的值

                               //ch[]是在dfs过程的数组

int f[][];

void init()  //初始化

{

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

    {

        lc[i] = ;

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

        lc[i] += abs(a[ch[j]][i] - a[ch[j + ]][i]);  //注意是+=

    }

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

    {

        for(int j=;j<i;j++)  //注意j<i

        {

            hc[i][j] = ;  //注意初始化

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

            hc[i][j] += abs(a[ch[k]][i] - a[ch[k]][j]);  //注意是+=

        }

    }

}

void dp()

{

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

    {

        cmin = min(i,c);

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

        {

            if(j == )  //这个边界是只选取一列，就把元素赋进去就好

            f[i][j] = lc[i];

            else

            if(j == i)  //这个边界是前i列都需要选取

            f[i][j] = f[i - ][j - ] + lc[i] + hc[i][j - ];

            else

            {

                f[i][j] = 0x7fffffff;  //注意初始化

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

                f[i][j] = min(f[i][j],f[k][j - ] + lc[i] + hc[i][k]);  //取最小值

            }

            if(j == c)  //如果这种状态存在，那我们就更新一下

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

        }

    }

}

void dfs(int rt)

{

    if(rt > n)  //

    {

        init();

        dp();

        return ;

    }

    if(r - gs +  == n - rt + )  //敲黑板！

    /*

    这个地方是一个剪枝，主要优化在了果rt和rt以后的元素必须全部取完，才能满足刚好有r个的条件，

    则必须rt，否则便会取到少于r个元素的情况。

    这样我们保证了rt > n时所有情况都刚好有r个，

    */

    {

        ch[gs++] = rt;  //注意是gs++而不是++gs

        dfs(rt + );

        ch[gs--] = ;  //注意是gs--而不是--gs

        return ;

    }

    dfs(rt + );

    if(gs <= r)  //如果已经选取满了

    {

        ch[gs++] = rt;  //但是还是需要这一步

        dfs(rt + );

        ch[gs--] = ;

    }

}

int main()

{

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

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

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

    scanf("%d",&a[i][j]);  //输入初始矩阵

    dfs();  //开始搜索

    printf("%d",minn);  //答案已经被更新，输出就行

    return ;

}

巴特西

[洛谷P2258][NOIP2014PJ]子矩阵(dfs)(dp)

题目描述

输入输出格式

f[i][j] = min (f[k][j-1] + hc[i][k] + lc[i])

最新文章

热门文章