(luogu2258)子矩阵

发表于 | 分类于 ， ，

一个不错的搜索题, 一个新的思路

思路:

dfs+dp

首先使用dfs枚举行, 枚举后用dp计算.

设$d(i,j)$表示在前$i$列中选择$j$列(一定选中第$i$列), 组成的所有子矩阵中分值的最小值.

则有如下状态转移方程:

其中, 式中的$dc(j,k)$表示$j$列与$k$列所有相邻元素绝对值差之和, $h(j)$表示$j$列中所有相邻元素的绝对差之和, 这两个量很容易地被预处理出来.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Mn(20);
inline int _abs(int x) { return x>=0 ? x : -x; }
inline int _min(int x,int y) { return x<y ? x : y; }
int n,m,r,c;
int a[Mn][Mn],d[Mn][Mn];    //题中矩阵和dp数组
int cho[Mn];    //已选行
int ans(0x3f3f3f3f);    //最终答案
int solve() ;
void dfs(int d) //枚举行
{
    if(d>r)
    {
        solve();
        return;
    }
    for(int i(cho[d-1]+1);i<=n-r+d;++i) //枚举边界优化
    {
        if(!isv[i])
        {
            cho[d] = i;
            dfs(d+1);
            cho[d] = 0;
        }
    }
}
int solve()
{
    memset(d,0x3f,sizeof d);
    for(int i(1);i<=m;++i)
    {
        int val(0);
        for(int j(1);j<r;++j)
            val += _abs(a[cho[j]][i]-a[cho[j+1]][i]);   //初始化当前行的相邻元素差之和
        d[i][1] = val;
        int val2[Mn]={0};
        for(int j(1);j<i;++j)
            for(int k(1);k<=r;++k)
                val2[j] += _abs(a[cho[k]][i]-a[cho[k]][j]); //初始化该行与其它行的相邻元素差之和
        for(int j(2);j<=i && j<=c;++j)
            for(int k(j-1);k<i;++k)
                d[i][j] = _min(d[i][j],d[k][j-1]+val+val2[k]);  //转移方程
        if(i>=c)	ans = _min(ans,d[i][c]);   //更新答案
    }
}
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",&a[i][j]);
    dfs(1);
    cout << ans;
    return 0;
}