【蓝桥杯C++】地宫取宝

2023-11-02 05:31

文章标签 c++ 蓝桥取宝地宫

本文主要是介绍【蓝桥杯C++】地宫取宝，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

致谢：AcWing 1212. 地宫取宝(普通 dp，重点理解）

AcWing 1212. 地宫取宝题解

1、思路怎么想？

（1）同理想框架，动态规划，状态表示和状态计算，

（2）状态表示：这个就很难了，是四维，

1）为什么是四维？

因为里面有坐标i,j从两个方向来，还有k件物品需要维护，另外还有最后一件物品的价值c需要维护，因为需要c来比较，是否取不取，这样就可以表示出，这个问题了。

类似于维护子序列和摘花生的结合。

为什么不能用二维，因为无法维护变量k这个东西，

为什么不用三维，因为无法维护变量c这个东西，这样就不能判断取还是不取，

所以综上，若在有几个变量，就是几维。

2）集合和属性怎样表示？

属性：数量

f[i , j ,k ,c]表示：所有从起点走到( i , j )，并已经取了k件物品，并且最后一件物品的价值为c的方案数，值是数量。

答案就是：f[n , m , k , i ] , i = 1.....13

表示：从起点走到(n,m)，且已经取了k件物品，且最后一件物品的价值是1或2或3...13 的所有方案的求和

（3）状态计算

2、代码怎么写？

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;//1、定义
const int N = 55 , mod = 1000000007;int n ,m ,k;
int w[N][N];
int f[N][N][13][14];//第三位为能得到宝藏的个数k,第四位为宝藏的价值int main()
{//2、输入scanf("%d%d%d" , &n , &m , &k);for( int i = 1 ; i <= n ; i++ )for( int j = 1 ; j <= m ; j++ ){scanf("%d" , &w[i][j]);w[i][j] ++;//为了处理边界，价值从1开始，0作为边界值 }//3、初始化初始位置的初值，即起点，在属性是数量时，要留意初始化顶点状态f[1][1][1][w[1][1]] = 1; //取左上角f[1][1][0][0] = 1;//不取左上角//4、dp过程for( int i = 1 ; i <= n ; i++ )for( int j = 1 ; j <= m ; j++ ){//1.左上角已经计算(初始化)过了if(i == 1 && j == 1) continue;//2.枚举所有方案数，即变量k的取值//枚举所有的最后取的(最大的)价值for( int u = 0 ; u <= k ; u++ )for( int v = 0 ; v <= 13 ; v++ ){int &val = f[i][j][u][v];//把f[i][j][u][v]的地址给val,因为后面要多次用到 f[i][j][u][v]，写成val更加方便 //3.不取的两种情况val = (val + f[i-1][j][u][v]) % mod;val = (val + f[i][j-1][u][v]) % mod;//4.取的两种情况//需要满足两条件，k大于0和w[i][j] == vif(u > 0 && w[i][j] == v){//5.枚举上一步的,所有的,价值小于当前宝藏价值v的,所有宝藏，实则是一个都是方案数的集合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;//右边来的}}}}//5、枚举从起点走到(n,m)，且已经取了k件物品，且最后一件物品的价值是1或2或3...13   的所有方案的求和int res = 0;for( int i = 1 ; i <= 13 ; i++ ) res = (res + f[n][m][k][i]) % mod;//应该注意，涉及mod，一般最后答案仍需再模printf("%d", res);return 0;
}