首页 > 其他分享 >蓝桥杯-地宫取宝

蓝桥杯-地宫取宝

时间:2024-05-09 11:44:22浏览次数:18  
标签:12 格子 val int 样例 蓝桥 宝贝 地宫 取宝

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

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

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

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

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

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

输入格式

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

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

输出格式

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

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

数据范围

1≤n,m≤50,
1≤k≤12,
0≤Ci≤12

输入样例1:

2 2 2
1 2
2 1

输出样例1:

2

输入样例2:

2 3 2
1 2 3
2 1 5

输出样例2:

14

题解:

f[n][m][k][c] 表示的是 从(1, 1) 到 (n, m), 选 k 个物品, 并且是以 c 结尾的所有方案的数量
因为 c是[0,12], 所以最终答案是 res + f[n][m][k][ci], ci 是[0, 12]

集合: 从(1, 1) 到 (n, m), 选 k 个物品, 并且是以 c 结尾的所有方案
属性: 数量

状态计算:

  1. 从(i, j)左边到(i, j)的, 不取第(i, j)件物品
  2. 从(i, j)上边到(i, j)的, 不取第(i, j)件物品
  3. 从(i, j)左边到(i, j)的, 第(i, j)件物品
  4. 从(i, j)上边到(i, j)的, 第(i, j)件物品

如下图:

注意: 我们f数组的第四维是代表 以 c 结尾, 但是题中 c = [0,12], 所以我们可以把每个 c 都加1, 也就是w[i][j] + 1. 这样我们 f 的第四维在没有取任何物品时就可以用 下标 0 表示了

看不懂的话, 可以先看这两个题, 摘花生最长上升子序列, 本题是前两道题的揉和

#include <bits/stdc++.h>
using namespace std;
const int N = 55, MOD = 1000000007;

int w[N][N], n, m, k;
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; // 初始话的跳过
            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][j - 1][u][v]) % MOD;  // 状态计算 1
                    val = (val + f[i - 1][j][u][v]) % MOD;  // 状态计算 2
                    if (u > 0 && w[i][j] == v)
                    {
                        for (int c = 0; c < v; c ++)
                            val = (val + f[i][j - 1][u - 1][c]) % MOD, // 状态计算 3
                            val = (val + f[i - 1][j][u - 1][c]) % MOD; // 状态计算 4
                    }
                }
        }
    int res = 0;
    for (int i = 0; i <= 13; i ++) res = (res + f[n][m][k][i]) % MOD;
    cout << res << endl;
    return 0;
}

觉得写的不错的话, 点个赞吧~

标签:12,格子,val,int,样例,蓝桥,宝贝,地宫,取宝
From: https://www.cnblogs.com/xxctx/p/18181795

相关文章

  • P10429 [蓝桥杯 2024 省 B] 拔河 题解
    思路通过动态规划计算出所有连续子序列的力量值之和,并将其存储在一个数组中然后排序,遍历一遍数组,找到相邻两个力量值之和的差的绝对值的最小值,然后输出这个答案就行了。时间复杂度大概是\(O(n^2\logn)\)。来个python的代码defmin_power_diff(n,a):#计算所有连续子序列......
  • 「高精度乘法+高精度加法」P10425 [蓝桥杯 2024 省 B] R 格式 题解
    解题思路题意分析:将浮点数乘以\(2^n\);四舍五入到最接近的整数。根据题意将\(d\times2^n\)分解为\(d\times2\times2\times2\times2……\),因为\(d\)长度小于等于\(1024\),所以可以使用高精度乘法的算法来实现一个小数乘以一个大于\(0\)的整数时,小数点位数本身不会......
  • P8754 [蓝桥杯 2021 省 AB2] 完全平方数
    原题链接题解分解n的质因子,如果为奇数就补一个由于大于\(\sqrt{n}\)的质因子最多不超过一个,所以我们筛小于\(1e6\)的质数code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;vector<int>prime;vector<int>minfac(1e6+3,0);intmain(){f......
  • 蓝桥杯-蚂蚁感冒
    长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左,有的朝右。每只蚂蚁都只能沿着杆子向前爬,速度是1厘米/秒。当两只蚂蚁碰面时,它们会同时掉头往相反的方向爬行。这些蚂蚁中,有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时,会把感冒传染给碰到的蚂蚁。请你计算,当所有蚂蚁......
  • 蓝桥杯-买不到的数目
    小明开了一家糖果店。他别出心裁:把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候,他就用这两种包装来组合。当然有些糖果数目是无法组合出来的,比如要买10颗糖。你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。大于17的任何数字......
  • 蓝桥杯国赛训练第一周
    P1491集合位置-洛谷|计算机科学教育新生态(luogu.com.cn)主要在于$A*$函数中估价函数,这里给出最好想也是我想出来的一种方法,也就是当黑白棋子各自都在对方的领域上,那么就可以考虑一种最小的消耗情况,也就是走一步顶两不,也就是黑白互换,那么此时所需要消耗的最小步数......
  • 【题解】爬山 蓝桥杯2024省B
    题目链接:P10429[蓝桥杯2024省B]拔河[蓝桥杯2024省B]拔河题目描述小明是学校里的一名老师,他带的班级共有\(n\)名同学,第\(i\)名同学力量值为\(a_i\)。在闲暇之余,小明决定在班级里组织一场拔河比赛。为了保证比赛的双方实力尽可能相近,需要在这\(n\)名同学中挑选......
  • 蓝桥杯-翻硬币
    小明正在玩一个“翻硬币”的游戏。桌上放着排成一排的若干硬币。我们用*表示正面,用o表示反面(是小写字母,不是零)。比如,可能情形是:**oo***oooo如果同时翻转左边的两个硬币,则变为:oooo***oooo现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个......
  • 蓝桥杯-带分数
    100可以表示为带分数的形式:100=3+69258/714还可以表示为:100=82+3546/197注意特征:带分数中,数字1∼9分别出现且只出现一次(不包含0)。类似这样的带分数,100有11种表示法。输入格式一个正整数。输出格式输出输入数字用数码1∼9不重复不遗漏地组成带分数表示的......
  • 蓝桥杯-四平方和
    四平方和定理,又称为拉格朗日定理:每个正整数都可以表示为至多4个正整数的平方和。如果把0包括进去,就正好可以表示为4个数的平方和。比如:5=0^2+0^2+1^2+2^27=1^2+1^2+1^2+2^2对于一个给定的正整数,可能存在多种平方和的表示法。要求你对4个数排序:0≤a......