背包问题九讲 2.0 beta1.2
背包问题九讲 2.0 beta1.2 本文题为《背包问题九讲》，从属于《动态规划的思考艺术》系列。 2011 年 9 月，本系列文章由原作者用 LaTeX 重新制作并全面修订，您现在看到的是 2.0 beta1.2 版本，修订历史及最新版本请访问 https://github.com/tianyic
矩阵快速幂与环形状压 DP：洛谷 P1357 花园详解
矩阵快速幂与环形状压 DP：洛谷 P1357 花园 详解 题目简述：有一个周长为 N 的环形花园，每个位置可以种 'C' 或 'P' 两种花。要求任意连续的 M 个位置中，'C' 的数量不能超过 K 个。求合法的种植方案数，对 10^9 + 7 取模。 数据范围：4 \leq N \leq 10^{
轮廓线 DP：网格图上的状态压缩艺术
轮廓线 DP (Broken Profile DP)：网格图上的状态压缩艺术 在处理棋盘、网格图的覆盖问题时（例如骨牌铺满问题、哈密顿路径计数），我们经常会想到状态压缩 DP。传统的状压 DP 通常是“逐行转移”的：用一个二进制数表示第 $i$ 行的状态，推导第 $i+1$ 行。但逐行转移的痛点在于
数论核心：乘法逆元详解与三大算法实现
数论核心：乘法逆元 (Modular Multiplicative Inverse) 详解与算法实现 在算法竞赛和密码学中，我们经常会遇到要求将最终结果对某个大质数（如 10^9+7 或 998244353）取模的情况。 对于加、减、乘法，模运算都满足分配律，我们可以一边计算一边取模。但是，除法是不
最长上升子序列（LIS）算法详解：从动态规划到路径还原
经典算法模型：最长上升子序列 (LIS) 详解 最长上升子序列 (Longest Increasing Subsequence, 简称 LIS) 是动态规划中最基础、也是极其重要的一个模型。 问题描述：给定一个长度为 n 的数组，找出一个最长的单调严格递增的子序列。子序列不需要在原数组中连续。 例如
最长上升子序列期望的两种巅峰解法：状压 DP 与杨表 RSK 对应
算法之美：最长上升子序列 (LIS) 期望的两种巅峰解法 —— 洛谷 P4484 深度剖析 (状压 DP vs 杨表与 RSK 对应) 求一个随机排列的最长上升子序列 (Longest Increasing Subsequence, LIS) 长度的期望，是一道极具数学和算法双重美感的题目。 对于数
算法之美：从暴力枚举到 O(1) 的概率论降维打击
算法之美：从暴力枚举到 O(1) 的概率论降维打击 —— 洛谷 P2911 [USACO08OCT] Bovine Bones G 数学解法详解 在算法竞赛中，求多个独立随机变量的和的分布是一个非常经典的模型。本题要求解的是：投掷三个面数分别为 A, B, C 的骰子，求出现概率（频次）最高的和；若
旅行商问题（TSP）与状态压缩动态规划详解
经典算法模型：旅行商问题 (TSP) 与状压 DP 旅行商问题 (Traveling Salesperson Problem, TSP) 是计算机科学中最著名的 NP-Hard 问题之一。 问题描述：给定一系列城市和每对城市之间的距离，求解访问每一座城市恰好一次并回到起始城市的最短回路。 因为它是
构造最短序列以满足特定整除二元组数量
巧妙的构造算法：特定整除二元组的最短序列 题目大意 给定一个数字 k（1 \leq k \leq 10^5），要求构造一个长度为 n 的序列 a_1, a_2, \dots, a_n，使得恰好存在 k 个二元组 (i, j) 满足 i < j 且 a_i \mid a_j（即
彻底搞懂状压 DP：NOIP 2017《宝藏》重构题解
彻底搞懂状压 DP：NOIP 2017《宝藏》重构题解 P3959 [NOIP 2017 提高组] 宝藏 题目背景 NOIP2017 D2T2 题目描述 参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n 个深埋在地下的宝藏屋， 也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。