蓝桥杯真题- 地宫取宝动态规划 / 记忆化搜索 (C++)

2438 阅读 2 评论 0 点赞

原题链接：蓝桥杯2014年第五届真题-地宫取宝

# [蓝桥杯真题] 地宫取宝 动态规划 / 记忆化搜索

## 1. 问题描述

基本可视作**搜索**的问题，但 **DFS 会超时**。

## 2. 动态规划法

### 2.1 最优值的定义及递归关系
#### 2.1.1 定义

```dp[x][y][num][maxValue]``` 为走到坐标```(x, y)```时, 不同行走方案总数的**最优值**(最大值), ```num```为背包中的物品总数, ```maxValue```为背包单个物品最大的价值。
此时未装入```(x, y)```处的物品。

#### 2.1.2 递归关系

1. 若装入```(x, y)``` 处的物品, 应先满足条件 ```c < C[x][y] && k > 0```, ```C```为物品价值数组。
```cpp
if (c < C[x][y] && k > 0){
	// 该点左方和上方
	int t1 = dp[x-1][y][num - 1][ C[x][y] ] + dp[x][y - 1][num - 1][ C[x][y] ];
	}
```
2. 不装入```(x, y)```处的物品
```cpp
// 该点左方和上方
int t2 = dp[x-1][y][num][maxValue] + dp[x][y-1][num][maxValue];
```
该点的最优值即为上述两种情况的最优值之和, 即:
```cpp
dp[x][y][num][maxValue] = (t1 + t2);    // 还应模那个大数
```

#### 2.1.3 边界值
```cpp
dp[1][1][0][maxValue] = 0;

// dp[1][1][1][]
```
### 2.2 完整代码 (AC)
最终结果为 ```dp[N][M][K][12]```
```cpp
// 蓝桥杯真题 地宫取宝
// 动态规划法
#include <cstdio>
const int maxn = 52;
const int maxnC = 13;
const int Q = 1000000007;   // 取模基数

int dp[maxn][maxn][maxnC][maxnC];     // 动态规划 dp[x][y][num][maxValue]
int C[maxn][maxn];      // 物品价值
int N, M, K;

int solve(){       // 迭代地动态规划
    for (int i = 1; i <= N; i++){       // x 坐标
        for (int j = 1; j <= M; j++){   // y 坐标
            for (int k = 0; k <= K; k++){   // 背包内物品总数
                for (int c = 0; c < maxnC; c++){      // 背包内单个物品的最大价值
                    if (i == 1 && j == 1){
                        if (k == 0 || (k == 1 && c > C[i][j]))
                            dp[i][j][k][c] = 1;
                        continue;
                    }

int t1 = 0, t2 = 0;
                    // 装当前物品
                    if (k > 0 && C[i][j] < c)
                        t1 = (dp[i][j-1][k-1][C[i][j]] + dp[i-1][j][k-1][C[i][j]]) % Q;
                    // 不装当前物品
                    t2 = (dp[i][j-1][k][c] + dp[i-1][j][k][c]) % Q;
                    dp[i][j][k][c] = (t1 + t2) % Q;
                }
            }
        }
    }
    return dp[N][M][K][maxnC-1];
}

int main(){
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            scanf("%d", &C[i][j]);

printf("%d", solve());
    return 0;
}

```

## 3. 记忆化搜索

### 3.1 基本思想
基本框架与```DFS``` 一致, 搜索中**保存子问题的值**, 在搜索过程中若**子问题的最优值已存在**, 直接使用而避免重复搜索。

### 3.2 完整代码 (AC)
```cpp
//
// 蓝桥杯题库 真题 地宫寻宝
// 记忆化搜索
#include <cstdio>
#include <cstring>
typedef long long LL;
using namespace std;
const int maxn = 51;
const LL Q = 1000000007;    // 基数
int K, N, M;    // 个数, 行数, 列数
int G[maxn][maxn];
// 记忆化搜索
LL dp[maxn][maxn][maxn][maxn];

// 方向变更
int xx[2] = {1, 0};
int yy[2] = {0, 1};

// 记忆化搜索, 因为物品价值可能为0, 所以 maxValue 初始值为 -1, maxValue + 1 就是基于此
LL dfsMem(int x, int y, int num, int maxValue){
    if (dp[x][y][num][maxValue + 1] != -1){     // 已有结果
        return dp[x][y][num][maxValue + 1];
    }

if (x == N-1 && y == M-1){
       if (num == K || (num == K-1 && G[x][y] > maxValue)){
           return dp[x][y][num][maxValue + 1] = 1;     // 记录
       }
    }

LL s = 0;
    for (int i = 0; i < 2; i++){        // 遍历下方和右方
        int cx = x + xx[i], cy = y + yy[i];
        if (cx < N && cy < M){
            if (maxValue < G[x][y] && num < K)
                s += dfsMem(cx, cy, num+1, G[x][y]) % Q;
            s += dfsMem(cx, cy, num, maxValue) % Q;
        }
    }

return dp[x][y][num][maxValue + 1] = s % Q;
}

int main(){
    scanf("%d%d%d", &N, &M, &K);
    for (int i = 0; i < N; i++){
        for (int j = 0; j < M; j++)
            scanf("%d", &G[i][j]);
    }
    memset(dp, -1, sizeof(dp));
    dfsMem(0, 0, 0, -1);

printf("%lld", dp[0][0][0][0]);
    return 0;
}
```

0.0分

12 人评分

本文分类：题解列表
浏览次数：2438 次浏览
发布日期：2020-02-16 16:07:55
本文链接：https://blog.dotcpp.com/a/66274

上一篇 > C语言训练-斐波纳契数列-题解(C语言代码)很简单的思路
下一篇 > [递归]母牛的故事-使用函数，循环实现(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯真题- 地宫取宝动态规划 / 记忆化搜索 (C++)

评论列表共有 2 条评论

发表评论取消回复

蓝桥杯真题- 地宫取宝 动态规划 / 记忆化搜索 (C++)

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 2 条评论

发表评论 取消回复

蓝桥杯真题- 地宫取宝动态规划 / 记忆化搜索 (C++)

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 2 条评论

发表评论取消回复