Oiclass P1226 题解
话不多说，这又是一道 DP 题 看题目就知道，这就是大名鼎鼎的最长不下降子序列 LIS 。所以我们用十分传统的五步（第六步是送的）解决这个问题 1. 划分阶段 我们的以每一个数划分阶段，也就是说每一个阶段存储的是以某个数结尾的子序列 2. 确定状态和状态变量 这里使用数组 \(f\) 来存放状态，数组 \(a\) 存储输入的数据，即状态 \(f_i\) 为以数字 \(a_i\) 结尾的最长不下降子
CodingCow's Blog - Code solves everything
Oiclass P1479 题解
这道题又又又又又是动规（我最近在学） 传统的五步： 1. 划分阶段 这里划分的阶段是在某个格子上时的最优解 2. 确定状态和状态变量 这里的状态数组 \(f\) 来进行存储，用数组 \(a\) 储存输入的数组。状态从他前面的格子获得，这些格子可能是： \[ a_{S},\ a_{S+1},\ a_{S+2}...a_{T-2},\ a_{T-1},\ a_{T} \] 3. 确定决策并写出状态转移
Oiclass P1221 题解
这道题不用多说也知道是 DP （看标签） 那么，究竟要怎样 DP 呢？下面依然是那熟悉的五步 1. 划分阶段 这里我采用的方法是划分爬到每一个位置，也就是以空间划分阶段 2. 确定状态和状态变量 OK，进入下一步 。在这里我定义的状态是在第 \(i\ (0<i≤n)\) 个位置时以跳到达和以爬到达的最优解，分别记为 \(jump_i\) 和 \(climb_i\) 3. 确定决策井写出状态转
Oiclass P3314 题解
这道题从题面就可以看出是经典的最长不下降子序列 对于这道一点都不简单的最长连续子序列和的模板题，我们还是直接暴力，代码： 123456789101112131415161718192021#include <iostream>using namespace std;int ans, n, a[1009];int main() { cin >> n; f
Oiclass P1220 题解
从标签题面可以看出这是一道动规（DP） 进入正题，依旧是传统的五步 1. 划分阶段 这里我的思路是将每公里的数值作为一个阶段，即 \(n\) 公里就有 \(n\) 个阶段，分别是: \[ 1, 2, 3, 4, 5, 6 ....(n-2),(n-1),(n) \] 2. 确定状态和状态变量 这里使用一个数组 \(f\) 来保存状态，即第 \(i\) 个状态为 \(f_i\) ，然后就没有了 3.
Oiclass P1235 题解
简单的一维动规 按照老师的要求 1. 划分阶段 非常容易的可以看出这道题目的阶段就是各个位置，即 \(i,\ j\) 。在这种划分下，每一种阶段的最优解可以由上一个阶段得到，且不会被右面的阶段所改变，故无后效性。综上，该题可以用 DP 求解 2. 确定状态和状态变量: 由 (1) 得：该题无后效性，故可用 递推的DP 进行求解，对于状态 \(i,\ j\) 的最优解，用 \(f_{i,j}\) 表
Oiclass P1213 题解
很明显，这道题是二分答案 那么，需要二分的是什么？有脑子都知道是，间距。那么求的究竟是最大值最小还是最小值最大呢？我们看到题目，我们需要求的是 “那么相邻两块土地之间的间隔的最大值” 也就是最小值最大。好的，那么框架有了，如下： 1234567891011bool check(int x);// l 是田之间的距离while (r - l > 1) { int mid =
Oiclass P3309 题解
这道是模拟题 思路如下 先输入 \(n\) 和 字符串 遍历字符串，如果没有出现过且\(当前排队人数<n\) ，将其标记，并将当前排队人数 \(+1\)，如果\(当前排队人数 ≥n\) ，不标记，同时将答案 \(+1\) 如果已经出现过了，将当前人数 \(-1\) 同时将其标位为出现 实现 实现起来很简单，首先定义一个整数 \(n\) 、一个字符串 \(str\) 、一个布尔数组 \(p