CodingCow's Blog - Code solves everything

这道题真的离谱 1. 划分阶段 对于这道题目，我以每一个字母为一个阶段，表示第一个字符串的前 \(i\) 个字母和第二个字符串的前 \(j\) 个字母之间的编辑距离（定义见题目） 2. 状态和状态变量 定义数组 \(f\) 用于存储状态，即 \(f_{i,\ j}\) 表示一个阶段（也就是(1) 里面提到的阶段），同时 \(a,b\) 分别是输入的两个字符串 3. 确定状态转移方程 这就是最难的部

这真是一场愉快的传球游戏 再次是传统的五步 1. 划分阶段 这里我划分的状态是：每次传球完一种状态 2. 确定状态和状态变量 对于状态变量，我定义一个二维数组 \(f\) ，对于 \(f_{i,\ j}\) 他表示的是在 \(i\) 次传球后，\(j\) 手上的球的数量。 3. 确定决策和状态转移公式 对于这道题，决策的方式稍稍有那么一点点复杂，对于一种状态 （\(f_{i,\ j}\)）它有以下

又是一道 DP 看到题目，我的第一反应就是：这鼹鼠是什么玩意儿？ 额，\(\Huge 搞错了\) 再来 下面是传统的五步 1. 划分阶段 以每一只耐造的鼹鼠为一个阶段，表示在这只鼹鼠前面（包括这只鼹鼠）可以打到的鼹鼠的数量 2. 确定状态和状态变量 这里使用两个数组 \(f,\ a\) ，分别存储状态和输入的数据 3. 确定决策和状态转移公式 因为每一只鼹鼠都可以和他前面的任何一只鼹鼠结合，所以我

这道题需要两次动规 (LIS DP) OK，再再再再是经典的五步 1. 划分状态 在这道题，我用每个人划分状态，每个人有两个状态，分别是以这个人结尾的最长不下降子序列长度和以这个人开头的最长不下降自序列的长度 2. 确定状态和状态变量 我使用三个数组 \(a,\ b,\ c\) 分别：存储输入的数据、存储状态一（以这个人结尾的最长不下降子序列长度）、存储状态二（以这个人开头的最长不下降自序列的长度

这道题思路稍稍有那么一点绕 先理解一下题目，交叉着一点还是挺难理解的，我们把样例的图片画出来的话大概是这样的： 截屏2023-01-05 14.38.33 我们仔细观察一下，会发现，不交叉的的几项在下面（南岸）形成了一个上升序列（也可以说是不下降序列），那么求有多少项不交叉是不是可以改成当北岸按升序排好时南岸的数的最长不下降子序列的长度？这就很好理解了。先把北岸排序，让南岸跟着动，然后求南岸

话不多说，这又是一道 DP 题 看题目就知道，这就是大名鼎鼎的最长不下降子序列 LIS 。所以我们用十分传统的五步（第六步是送的）解决这个问题 1. 划分阶段 我们的以每一个数划分阶段，也就是说每一个阶段存储的是以某个数结尾的子序列 2. 确定状态和状态变量 这里使用数组 \(f\) 来存放状态，数组 \(a\) 存储输入的数据，即状态 \(f_i\) 为以数字 \(a_i\) 结尾的最长不下降子

这道题又又又又又是动规（我最近在学） 传统的五步： 1. 划分阶段 这里划分的阶段是在某个格子上时的最优解 2. 确定状态和状态变量 这里的状态数组 \(f\) 来进行存储，用数组 \(a\) 储存输入的数组。状态从他前面的格子获得，这些格子可能是： \[ a_{S},\ a_{S+1},\ a_{S+2}...a_{T-2},\ a_{T-1},\ a_{T} \] 3. 确定决策并写出状态转移

这道题不用多说也知道是 DP （看标签） 那么，究竟要怎样 DP 呢？下面依然是那熟悉的五步 1. 划分阶段 这里我采用的方法是划分爬到每一个位置，也就是以空间划分阶段 2. 确定状态和状态变量 OK，进入下一步 。在这里我定义的状态是在第 \(i\ (0<i≤n)\) 个位置时以跳到达和以爬到达的最优解，分别记为 \(jump_i\) 和 \(climb_i\) 3. 确定决策井写出状态转

这道题从题面就可以看出是经典的最长不下降子序列 对于这道一点都不简单的最长连续子序列和的模板题，我们还是直接暴力，代码： 123456789101112131415161718192021#include <iostream>using namespace std;int ans, n, a[1009];int main() { cin >> n; f

从标签题面可以看出这是一道动规（DP） 进入正题，依旧是传统的五步 1. 划分阶段 这里我的思路是将每公里的数值作为一个阶段，即 \(n\) 公里就有 \(n\) 个阶段，分别是: \[ 1, 2, 3, 4, 5, 6 ....(n-2),(n-1),(n) \] 2. 确定状态和状态变量 这里使用一个数组 \(f\) 来保存状态，即第 \(i\) 个状态为 \(f_i\) ，然后就没有了 3.