每日算法打卡：地宫取宝

算法
1.2k words

原题链接

1212. 地宫取宝

题目难度：中等

题目来源：第五届蓝桥杯省赛C++ A/B/C组,第五届蓝桥杯省赛Java B/C组

题目描述

X 国王有一个地宫宝库，是 $n \times m$ 个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是 $k$ 件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 $k$ 件宝贝。

输入格式

第一行 3 个整数，$n,m,k$，含义见题目描述。

接下来 $n$ 行，每行有 m 个整数 $C_i$ 用来描述宝库矩阵每个格子的宝贝价值。

输出格式

输出一个整数，表示正好取 $k$ 个宝贝的行动方案数。

该数字可能很大，输出它对 $1000000007$ 取模的结果。

数据范围

$1 \le n,m \le 50$,
$1 \le k \le 12$,
$0 \le C_i \le 12$

输入样例1：

1
2
3
2 2 2
1 2
2 1

输出样例1：

1
2

输入样例2：

1
2
3
2 3 2
1 2 3
2 1 5

输出样例2：

1
14

题目分析

这道题和之前的摘花生的题目是十分类似，其实就是一个扩展与限制，这里有一个限制就是需要以严格递增的顺序拿，另一个限制就是最后拿到的数量必须是k件

我们仍然是采用集合的DP思想，对于集合$f(i,j,k,c)$这里的i，j表示当前的坐标，k表示当前取到了多少个，c表示取到物品的数值，确保其是递增的。他的意思就是，从七点走到i，j取了k件物品，最后一个物品的价值是c的所有合法方案的集合

对于这个集合如何进行状态计算，就是如何进行状态划分，因为这个题目的状态非常多，就需要逐步分析，就像剥洋葱一样，一层一层细分，第一层是按照位置分，分别从上向下走和从左向右走两种，第二层是按照第i，j个物品是否取得划分，那么对于取的情况下，对于每一个上一个物品的数值是多少再次进行划分

我们逐步分析每一种情况的状态计算具体是什么

对于从上往下的不取的情况$f(i,j,k,c)=f(i-1,j,k,c)$因为不取，所以对k和c没有任何影响，对于从左往右的情况也是相同的

对于取的情况来说，他需要满足在取的时候这个位置上的权值必定为c，因为在取之后c一定是之前所有取到的数值的最大值

这个问题我们需要考虑一下边界的初始化问题，起点有两种情况，第一种就是选择第一个位置的数字$f(1,1,1,w(1,1)=1$，如果不选择第一个位置的数字就是$f(1,1,0,-1) = 1$当然这里的-1是不合法的，我们可以给所有的权值加1即可

示例代码

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<cstring>
#include<algorithm>
using namespace std;

const int N = 55,MOD=1000000007;

int n,m,k;
int w[N][N];
int f[N][N][13][14];

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w[i][j];
            w[i][j]++;
        }
    }
    
    // 初始化
    f[1][1][1][w[1][1]] = 1; // 表示选择第一个数，是一类方案
    f[1][1][0][0] = 1; // 表示不选第一个数，是一类方案
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i==1&&j==1) continue; // 表示1，1位置已经初始化过了
            for(int u=0;u<=k;u++)
            {
                for(int v=0;v<=13;v++)
                {
                    int &val = f[i][j][u][v]; // 起别名方便表示
                    val = (val+f[i-1][j][u][v])%MOD; // 表示不选择这个数
                    val = (val+f[i][j-1][u][v])%MOD;
                    if(u>0&&v==w[i][j]) // 如果选择
                    {
                        for(int c=0;c<v;c++)
                        {
                            val = (val + f[i-1][j][u-1][c])%MOD;
                            val = (val + f[i][j-1][u-1][c])%MOD;
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i=0;i<=13;i++) ans = (ans + f[n][m][k][i])%MOD;
    cout<<ans<<'\n';
    return 0;
}


Comments