修补骑士

题解

/ 注册

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

题解 | #花店橱窗#

一个经典的板子dp题目，时间复杂度不高，可以使用经典dp形式我们定义dp[r][p]，就是第r个花朵放在第p个花瓶的美观度（有点类似背包），首先进行剪枝操作：由于每个花都要放，第i朵花只能放在第i个花瓶到第v - (f - i)个花瓶之间，这是为了预留足够的空间之后对于每一种dp[r][p]，我...

C++ 动态规划

2025-06-19

1 12

题解 | #石子合并#

非常经典的区间dp题啊，这种题的数据结构不大，可以从一些比如n3复杂的的方式入手对于状态转移方程，区间[a,b]与[x,y]合并，代价就是：两个区间之前合并到这一步所记录的代价+他们自己的代价。也就是说我们需要维护两个数组：dp与presum来分别记录路径代价与区间重量总和，对于每个大的区间，可以...

C++ 动态规划模拟

2025-06-19

1 16

题解 | #合并回文子串#

这道题的思路很简单，就是普通的dp，甚至比起单个字符串判断最大子回文长度还要简单。但是在细节上有相当多的地方需要注意由于数据量是50所以说可以用一些时间复杂度比较神秘的dp方法，这里我们模仿普通单个字符串回文的求法，设一个四维dp数组，说明a的[l1,r1]区间与b的[l2,r2]区间组成的字符串...

C++ 数组动态规划数学

2025-06-01

1 22

题解 | #Butterfly#

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

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

2025-04-26

1 35

题解 | #Music Problem#

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

C++ 动态规划设计

2025-04-21

1 43

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

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

C++ 动态规划

2025-04-18

1 32

题解 | #小A买彩票#

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

C++ 动态规划

2025-04-18

1 39