【算法ABC】动态规划 - 常见普通题型及状态表示

【算法ABC】动态规划 – 常见普通题型及状态表示

上一节我们讲了序列型动态规划,一点精髓就是动态规划最重要的是状态间的顺序(阶段划分)。这个顺序可能是题目给你的,也可能是需要自己转化出来的,确定了这个顺序之后,就可以类比序列型动态规划做了。可以说,熟练掌握了序列型动态规划,你就在代码层面和逻辑层面掌握了动态规划,其他所有题目都可以使用自己的智慧解答出来。 那么接下来,各位同学要做的就是多做题、多接触不同类型...
【算法ABC】动态规划 - 序列型

【算法ABC】动态规划 – 序列型

序列型动态规划 这类题目上来一定丢给你一个类似序列东西,比如说一个数列 {a_n},一个字符串 S或者说是一排房子。总之就是给你一堆东西,它们显式或者隐式地存在一种从前先后的顺序。 对于这种类型的题目,阶段地划分就按照序列从前往后的位置顺序进行,考虑到了第 i 个位置,那么就位于阶段 i,结下来要往阶段 i+1 转移。状态设计的时候,也会将序列中的位置作为状...
Codeforces 1295F Good Contest

Codeforces 1295F Good Contest

题目大意 有一个未知的序列 a_1, a_2, \cdots, a_n,每一个数字 a_i 等概率地可能是区间 [l_i, r_i] 内的任意一个整数,试问这个序列单调不递增的概率是多少,答案对 998244353 取模。 数据范围: 2\leq n \leq 50 0 \leq l_i \leq r_i \leq 998244351 题目链接:http...
LeetCode 5154. 翻转子数组得到最大的数组值

LeetCode 5154. 翻转子数组得到最大的数组值

题目大意 给你一个数组 A, 你可以将它的一个子区间翻转(也可以不翻转),求最大的 \sum_i |A_i – A_{i + 1}| 分析 首先,题目有一些特殊情况: 不反转 翻转区间从原区间头开始 翻转区间到原区间尾结束 不看上面的三种特殊情况,普通情况可以被描述成这样(虚线是包裹住的是要翻转的区间): 很容易知道一点:翻转区间操作仅与边...
ST表

ST表

简介 给定一个长度为 n 的数组,支持 O(1) 查询区间最值。 使用前,调用 init() 函数初始化 ST,然后使用 query() 函数查询区间最值。 当前代码实现区间最小值问题,区间的最大值,最大公约数等均可以查询。 原理 预处理出原区间内长度为 1, 2, 4, \cdots, 2^k 的子区间的答案,此预处理的复杂度为 O(n \log n)。 ...
后缀数组

后缀数组

简介 给定一个 0-Based 字符串 Str,将它的所有后缀进行排序。 数组 sa[i] 中保存排名第 i 的后缀的在字符串的那个位置,数组 rank[i] 表示从位置 i 开始的子串的排名。 数组 height[i] 表示排名第 i 的字符串和排名第 i+1 的字符串的公共前缀长度。 代码 namespace SuffixArray{ const...
AC自动机

AC自动机

简述 处理多模式串匹配问题,初始化后(init),先插入所有模式串(insert),然后构建AC自动机(build),最后进行匹配(next)。 假设模式串集合为 {S},目标串为 T,那么算法复杂度为 O(Simga_i |S_i| + |T|)。 原理 等待填坑… 代码 class AhoCorasiek{ protected: co...
Hello World

Hello World

H1 H2 H3 H4 H5 H6 列表项A A B 列表项B 列表项C 列表项D A B 1 -1 -1 1 代码高亮 #include <cstdio> using namespace std; int main(){ puts("Wordpress Yes."); return 0; } ...