修补骑士

题解

/ 注册

全部文章 / 题解（共4篇）

题解 | #Butterfly#

修补骑士一看见题面就放弃的差不多了。这里主要是绝大多数人可能会惯性思维的认为是从中间开始，之后往四边扩展验证，明显实现起来太过麻烦并且时间复杂度过大，不过考虑构造的思路是没有错的对于每一个点，我们考虑积累三个元素：向上的延伸，向左上的延伸与向右上的延伸，对于一个方格（假设为右下角），我们先找到向上...

C++ 动态规划几何枚举图

2025-04-26

1 11

题解 | #Music Problem#

题目名称：音乐问题问题描述：强迫症患者HH只有在歌曲结束时处于整点时间（即分钟和秒均为0）才能停止听歌他初始时间为12:00:00，且一旦开始听歌就只能通过满足上述条件的方式停止给定若干首歌曲的时长，请判断是否存在一种选歌方式（每首歌最多选一次），使得HH能在某个整点时间停止听歌。输入描述...

C++ 动态规划设计

2025-04-21

1 15

题解 | #「木」迷雾森林#

哎呦我操帕秋莉怎么这么坏啊这题直接浪费了我大好的一个上午加中午的学习时间，我现在正在一边啃着我最爱的腰果一边控诉这道题：思路上很明显，虽然说这题一股子BFS味，但是为了求所有方式，复杂度上DFS又不合适，我们自然而然想到了DP。“情况”也很明显——不同位置走到的方式，同时只能向上向右走又保证了有...

C++ 动态规划

2025-04-18

1 11

题解 | #小A买彩票#

哇，这也是DP？修补骑士一开始当背包来想：我们要写4个数组来DP吗？每一个都记录可行的最大次数吗？但他很快发现——这个主要是可以积累，你不知道他上一个可行究竟剩下来多少！看了看题解：我们要维护“成功数量”与“剩余数量”，只写一维不好维护，我们就拿不到每种成功情况下对应的剩余，就没法持续DP运算。...

C++ 动态规划

2025-04-18

1 16