标签:动态规划

发布于2022-05-26

2018年第九届蓝桥杯国赛-E. 搭积木

小明对搭积木非常感兴趣。他的积木都是同样大小的正立方体。 在搭积木时,小明选取 m 块积木作为地基,将他们在桌子上一字排开,中间不留空隙,并称其为第0层。 必须满足三种堆放规则,问总共有多少种放法?

发布于2022-05-26

2018年第九届蓝桥杯国赛-B. 激光样式

x星球的盛大节日为增加气氛,用30台机光器一字排开,向太空中打出光柱。 安装调试的时候才发现,不知什么原因,相邻的两台激光器不能同时打开! 国王很想知道,在目前这种bug存在的情况下,一共能打出多少种激光效果? 显然,如果只有3台机器,一共可以成5种样式,即: - 全都关上(sorry, 此时无声胜有声,这也算一种) - 开一台,共3种 - 开两台,只1种 30台就不好算了,国王只好请你

发布于2022-03-22

2018年第九届蓝桥杯省赛-D.测试次数

X 星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的 2 楼。 如果手机从第 7 层扔下去没摔坏,但第 8 层摔坏了,则手机耐摔指 =7。 特别地,如果手机从第 1 层扔下去就坏了,则耐摔指数 =0。 如果到了塔的最高层第 n 层扔没摔坏,则耐摔指数 =n。

发布于2022-03-07

2017年第八届蓝桥杯省赛-H.包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N 种蒸笼,其中第 i 种蒸笼恰好能放 Ai 个包子。每种蒸笼都有非常多笼,可以认为是无限笼。 每当有顾客想买 X 个包子,卖包子的大叔就会迅速选出若干笼包子来,使得这若干笼中恰好一共有 X 个包子。 小明想知道一共有多少种数目是包子大叔凑不出来的。

发布于2021-12-19

信息学竞赛模板(十七)— 最长上升子序列

最长上升子序列(Longest Increasing Subsequence),简称LIS,也有些情况求的是最长非降序子序列,二者区别就是序列中是否可以有相等的数。

发布于2021-12-16

2015年第六届蓝桥杯省赛-J. 生命之树

在 X 森林里,上帝创建了生命之树。 他给每棵树的每个节点(叶子也称为一个节点)上,都标了一个整数,代表这个点的和谐值。 上帝要在这棵树内选出一个非空节点集 S,使得对于 S 中的任意两个点 a,b,都存在一个点列 {a, v1, v2, ..., vk, b} 使得这个点列中的每个点都是 S 里面的元素,且序列中相邻两个点间有一条边相连。 在这个前提下,上帝要使得 S 中的点所对应的整数的和尽

发布于2021-12-16

2015年第六届蓝桥杯省赛-I. 垒骰子

赌圣 atm 晚年迷恋上了垒骰子,就是把骰子一个垒在另一个上边,不能歪歪扭扭,要垒成方柱体。 经过长期观察,atm 发现了稳定骰子的奥秘:有些数字的面贴着会互相排斥! 我们先来规范一下骰子:1 的对面是 4,2 的对面是 5,3 的对面是 6。 假设有 m 组互斥现象,每组中的那两个数字的面紧贴在一起,骰子就不能稳定的垒起来。 atm 想计算一下有多少种不同的可能的垒骰子方式。 两种垒骰

发布于2021-12-16

2015年第六届蓝桥杯省赛-G. 牌型种树

小明被劫持到X赌城,被迫与其他3人玩牌。 一副扑克牌(去掉大小王牌,共52张),均匀发给4个人,每个人13张。 这时,小明脑子里突然冒出一个问题: 如果不考虑花色,只考虑点数,也不考虑自己得到的牌的先后顺序,自己手里能拿到的初始牌型组合一共有多少种呢?

发布于2021-12-13

2014年第五届蓝桥杯省赛-I. 地宫取宝

X 国王有一个地宫宝库。是 n×m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。 地宫的入口在左上角,出口在右下角。 小明从入口出发,要求他只能向右或向下行走。 走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。 当小明走到出口时,如果他手中的宝贝恰好是 k 件,则这些宝贝就可以送给小明。 请你算一算,他有多少种不同的行动方案能获

发布于2021-12-02

2012年第三届蓝桥杯省赛-J.取球游戏

今盒子里有 n 个小球,A、B 两人轮流从盒中取球,每个人都可以看到另一个人取了多少个,也可以看到盒中还剩下多少个,并且两人都会采取最优策略。 我们约定: 每个人从盒子中取出的球的数目必须是:1,3,7 或者 8 个。轮到某一方取球时不能弃权!A 先取球,然后双方交替取球,直到取完。被迫拿到最后一个球的一方为负方。 请编程确定出在双方都不判断失误的情况下,对于特定的初始球数,A是否能赢?