数位dp

题目描述 有一长度为 N(1<=Ｎ<=10) 的地板，给定两种不同瓷砖：一种长度为 1，另一种长度为 2，数目不限。要将这个长度为 N 的地板铺满，一共有多少种不同的铺法？ 输入格式 输入有多组，每组只有一个数 N，代表地板的长度 输出格式 对于每组数据，输出一个数，占一行，代表所有不同的瓷砖铺放方 ......

题目描述 如果将课本上的汉诺塔问题稍做修改：给定 N 只盘子，3 根柱子，但是允许每次最多移动相邻的 M 只盘子（当然移动盘子的数目也可以小于 M）, 最少需要多少次？ 输入格式 输入数据仅有一行，包括两个数 N 和 M（0<=M<=N<=8） 输出格式 仅输出一个数，表示需要移动的最少次数 #in ......

傻逼博客园，写好的文章不是自动保存在草稿箱，而是这个打开的网页。然后傻逼 Windows 自动更新使得断电退出这个网页，写的几百行文章没了。操了。 全路径计数 关于全路径计数，大前天 已经给出两例，今日再加一例。一般来说，点权和边权的做法是不一样的，所以分开来说。 全路径颜色统计（点权） https ......

数位DP 数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。 数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征： 要求统计满足一定条件的数的数量（即，最终目的为计数）； 这些条件 ......

区间DP 区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。 例题 石子合并 洛谷1880 #include<bits/stdc++.h> using namespace std; int n,i,j,k,l,ma,mi,a ......

树形DP 树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。 例题 没有上司的舞会 洛谷1352 #include<bits/stdc++.h> using namespace std; int n,i,x,y,b[6005],f[6005][2]; vecto ......

状压DP 状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。 例题 售货员的难题 洛谷1171 #include<bits/stdc++.h> using namespace std; int n,i,j,k,min1,a[25][25],f[1050000][25]; int ......

DP优化 单调队列优化 Watching Fireworks is Fun CF372C #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,d,i,j,k,l,r,ma,f[2][150005],g[1 ......

背包DP 二进制分组优化 考虑优化。我们仍考虑把多重背包转化成 0-1 背包模型来求解。 预处理物品数量是2的次方。且要覆盖物品数量的点。即2 n次方+1到k index = 0; for (int i = 1; i <= m; i++) { int c = 1, p, h, k; cin >> p ......

线性DP 最长公共子序列 O(n*m)写法 int a[MAXN], b[MAXM], f[MAXN][MAXM]; int dp() { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i] == b[j]) f[i] ......

题目链接 [https://leetcode.cn/problems/maximum-subarray/description/](53. 最大子数组和 "https://leetcode.cn/problems/maximum-subarray/description/") 思路 分析动态规划题目 ......

题意（简化版） 给出一个长度为 $2n$ 的序列 $a_i$，求将序列分割为若干个长度为偶数的区间，满足每个区间内都不含绝对众数（出现次数严格大于长度的一半的数）的方案数。 $n\le 500000,,a_i\le2n$ 解法 解法和官方题解大致相同，虽然官方题解我也没看太明白（ 显然一定在偶数出断 ......

题目 D. Program 题意 给一个长度为n的‘+’，‘-’序列，表示+1和-1 在给m个查询，问忽略[l,r]之间的序列，能走到多少个不同的数字 思路 分为前后缀计算，前缀计算比较简单关键是后缀计算 后缀上，需要关注能够到达的最小值和最大值 定义sufL[i]和sufR[i]分别表示为到达的最 ......

树形DP 给出一棵树，要求以最少代价（或最大收益）完成给定的操作。 基本操作 树的遍历，用DFS从根节点开始进行记忆化搜索 从树最深处开始往回进行DP，用子节点dp值来更新父节点dp值 复杂度分析：遍历每个节点，总复杂度为$O(n)$ 例题 某大学有 $n$ 个职员，编号为 $1\ldots n$。 ......

描述 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能超过前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统，因此有可能不能拦截所有的导弹。怎么办呢？请帮助计算一下最 ......

描述 最近越来越多的人都投身股市，阿福也有点心动了。谨记着“股市有风险，入市需谨慎”，阿福决定先来研究一下简化版的股票买卖问题。 假设阿福已经准确预测出了某只股票在未来N天的价格，他希望买卖两次，使得获得的利润最高。为了计算简单起见，利润的计算方式为卖出的价格减去买入的价格。 同一天可以进行多次买卖 ......

博弈DP解决的是两人轮流操作，且没有平局的两人博弈游戏，和博弈问题的形式相同。 博弈论dp正推会有后效性,这是无法解决的 所以一般博弈论dp会选着逆推 但实际上逆推也不好写，所以这时候一般会以记忆化搜索dp的形式来写博弈论dp ......

所有代码的开头头文件，宏定义和命名空间如下 #include <bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define ll long long # ......

引入 按顺序排列的的三个矩阵 M1,M2,M3 计算三个矩阵相乘结果，有两种乘法 （M1 M2) M3 M1(M2 M3) 但两种乘法计算次数不同 三个矩阵维度如下 4 * 5 5 * 6 6 * 7 第一种计算次数 4 * 5 * 6 + 4 * 6 * 7 第二种计算次数 5 * 6 * 7 + ......

视频链接：https://www.bilibili.com/video/BV1EK411K7Eb/ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=1010; i ......

视频链接：https://www.bilibili.com/video/BV1KK4y1e7t7/ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=1010; i ......

最长递增路径 题目 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。 对于每个单元格，你可以往上，下，左，右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。 链接 DP 但是依旧不能覆盖所有的情况 class Solution { pub ......

给定一棵树，树中包含 nn 个结点（编号11~nn）和 n−1n−1 条无向边，每条边都有一个权值。 请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。 输入格式 第一行包含整数 nn。 接下来 n−1n−1 行，每行包含三个整数 ai,bi,ciai,bi,ci，表示点 aiai 和 b ......

「学习笔记」数位 DP 意义不大的题不写了。 点击查看目录 概述 数位 DP 一般用来解决「在一个较大的区间内统计具有一定特征的数的数量」的问题。 数位 DP 一般有两种做法： 递推法：首先需要预处理出具有一定条件的数的个数，然后将上限按数位拆分开来考虑贡献。 暴搜法：直接记忆化搜索具有特定条件的数 ......

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 这周比较忙，上周末的双周赛题解现在才更新，虽迟但到哈。上周末这场是 LeetCode 第 101 场双周赛，整体有点难度，第 3 题似乎比第 4 题还难一些。 周赛大纲 2605. 从两个 ......

数位DP 数位DP通常指在$[l,r]$区间中有多少个满足条件$k$的个树 常见的数据范围都很大 也就是说， 把数字的枚举，变成数字的构造 不要把数字看作是$10^{18}$ 而把数字看作是$18$位数的填数过程 就是把原本枚举的问题转化为了构造的问题 然而数位dp常通过记忆化搜索实现 tips: ......

数位 $\text{dp}$ 前言 谨慎学习此算法。 算法讲解 AcWing 1081.度的数量 题意分析：你看到这道题，是不是无从下手？其实题目就是让我们求在 $x \sim y$ 中，有多少个数分解成 $B$ 进制后仅有 $k$ 位为 $1$，其余均为 $0$； 考虑暴力：从 $x$ 枚举到 $ ......

石子合并 - 区间动态规划 题意 设有 $N$ 堆石子排成一排，其编号为 $1 \sim N$。 每堆石子有一定的质量，可以用一个整数来描述，现在要将这 $N$ 堆石子合并成为一堆。 每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的 ......

蒙德里安的梦想 - 状态压缩动态规划 题意 求把 $N \times M$ 的棋盘分割成若干个 $1 \times 2$ 的长方形，有多少种方案。 样例输入 2 4 样例输出 5 算法 状态压缩动态规划 (状压DP) $\to$ OI-WIKI 状态压缩，顾名思义，就是将某一种状态压缩成容易储存的形 ......

1. 最大的和 来源《信息学奥赛一本通》 原题链接 题目描述 对于给定的整数序列 $A=\lbrace a_1,a_2,…,a_n \rbrace$，找出两个不重合连续子段，使得两子段中所有数字的和最大。 我们如下定义函数 $d(A)$： $$d(A) = max_{1≤s_1≤t_1<s_2≤t_ ......