数位dp
我要开始做USACO的DP以对抗智力下降
P6205 [USACO06JAN] Dollar Dayz S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题解：完全背包,__int128，傻逼题 ``` #include using namespace std; __int128 f[10001]; void write ......
7.31 day8dp
100+80+60+0=240 T1 简单dp，每条链在lca处统计 T2 考虑只需要维护奇偶性，所以bitset维护即可 T3 二分答案， T4 写了80分的，但是没调出来（为什么暴力都比正解难写很多 直接设$f_{x,y}$为选到第x个点，y个集合的方案数，要保证选一个点是祖先都已经选完，此时祖 ......
【笔记】DP 优化（WIP）
# 7.30 DP ## 凸相关 决策单调性、斜率优化、凸、四边形不等式，都是凸相关。 ### 前置知识 四边形不等式：交叉小于包含。$l_10$ 则没事，更新 $sum:=sum-1$。 - 否则拿不进来，反悔，撤销之前匹配的 $len$。设 $link_{len}$ 表示一个地方，跳过去之后 $ ......
abc312d <dp, 括号匹配方案数>
### 题目 [D - Count Bracket Sequences](https://atcoder.jp/contests/abc312/tasks/abc312_d) ### 思路 - `dp[i][j]`为考虑前$i$个位置，待匹配的`(`有$j$个的方案数； ### 代码 点击查看代码 ......
dp题型总结
## dp专项训练与题型总结（持续更新） [toc] ### 常见题型：（常规模型） 树上dp 区间dp lis 背包 等等。 经过n次考试的洗礼，我发现我的dp能力太弱了,所以决定来专练一下 ### 刷题1：雷涛的小猫 （我称此类题型为EZ模型） https://www.luogu.com.cn/ ......
Codeforces Round 105 (Div. 2) - D. Bag of mice DP 或 记忆化搜索 求概率
# [D. Bag of mice](https://codeforces.com/contest/148/problem/D) ## 题意 待补充~ ## 思路 可利用 DP 或者记忆化搜索求解本问题，实际上这两个方法等价。 ## 代码 - 记忆化搜索 ```cpp //>>>Qiansui #i ......
DP 套 DP 学习笔记
## 【例题 1】单调栈自动机 引自 。 >对于一个数，你可以进行任意次操作，每次操作可以删去数字相同的连续一段，例如你可以把 $1122331$ 变成 $22331$，$11331$，$11221$ 或者 $112233$。当然，如果整个数都是连续的一段，那么我们可以将它变成 $0$。 > >记把 ......
换根DP
换根法思路： 1. 自下而上递推； 2. 自上而下递推。 ### P3478 [POI2008] STA-Station #### 题目描述：  **算法：**dp **做法：**由于要一笔将所有黑块都划出来。所以我们状态转移方程应尽可能从左上角或者右下角的黑方块转移过来。$$f[i,j] = ......
ETHERNET/IP转PROFIBUS-DP网关EtherNet/IP与Profibus DP通讯网关
大家好，今天要给大家介绍一款非常神奇的通讯网关捷米特JM-DPM-EIP！这款产品可以将各种PROFIBUS-DP从站接入到ETHERNET/IP网络中，真是一款神奇的产品啊！你是否想过，如果没有这款产品，PROFIBUS-DP从站和ETHERNET/IP网络之间该怎么通讯呢？让我们来看看这款产品到... ......
替代LT8611芯片设计|CS5218设计方案|DP++转HDMI4K30HZ转换芯片方案
ASL北京集睿致远研发CS5218 DP转HDMI 4K 30HZ 转换芯片，支持高达3840 x2160@30Hz 或者4096x2160@30Hz ，主要用于设计TYEPC 拓展坞和DP转接线的开发与应用。CS5218芯片设计电路： CS5218替代LT8611芯片包括2路双模DP电缆适配器寄存 ......
DP综合
**DP**是OI竞赛中应用**特别广泛**的一类算法 ~~（通常我用来骗分打表）~~ 下面进入正题 ### Part 1.01背包 01背包的题目要求通常是给你一些物品，每个物品有它的重量和价值，你有一定的空间来装这些东西，一种只有一个，问能拿走最多多少价值的物品。就相当于你在逃难中只有一个包，你 ......
常见 DP 模型学习笔记
一些经典的 DP 类型。 # I.数位 DP 数位 DP 归在此处，无论是高位往低位还是低位往高位。需要注意数位 DP 的本质是一种按位比较的贪心思想，因而可以加以扩展。 ## I.[[CQOI2013]二进制A+B](https://www.luogu.com.cn/problem/P4574) ......
DP 各类优化学习笔记
通过某些 trick 以优化复杂度。 # I.单调队列/单调栈 单调队列/单调栈优化 DP 是对简单决策单调性 DP 的常见优化。 ## I.[[HNOI2005]星际贸易](https://www.luogu.com.cn/problem/P2317) 第一问直接背包一下就行，是模板。 然后，因为 ......
DP 常见 patterns 学习笔记
DP 时可行的某些套路。 # I.DP 的图论化 将 DP 式子实际化有时会提供新思路。 **这可以被看作是同一个 DP 式解决不同的问题，因此一定程度上考验出题的功夫**。 ## I.[[UOJ#76][UR#6]懒癌](https://uoj.ac/problem/76) 现在考虑某一局面。 此 ......
7.25 day2数据结构优化dp
战绩： 100+100+20+54 = 374 T1 据lxl说是为了成绩好看加的题，难度大概cspjT1 T2 朴素dp然后树状数组优化一下 T3 赛时脑抽链，写了个dp，一直想优化dp，其实贪心就好了，过程更加简洁，优化很显然 先将区间剖分成两段端点$s_i=s_j$相同的多条线段 将区间每个点 ......
树形DP
## [P3565 [POI2014] HOT-Hotels ](https://www.luogu.com.cn/problem/P3565) ### $solution 1$: 先说一下我想到的 $O(n^2)$ 算法。 首先不难发现，如果三个点两两距离相等，那么一定存在一个中心点，使得中心点到 ......
数位dp
### 数位dp的一般套路 **问题形式** 给你一个条件 $A$ ,然后询问值大小在 $[L,R]$ 中有多少满足条件的数 这个问题暴力去做一般是 $\mathcal{O}(R)$ 的时间复杂度,但是通过数位dp我们可以把这个东西优化到 $\mathcal{O}(\log_{10}R)$ **求解 ......
区间dp
### P1880 [NOI1995] 石子合并（破环成链+石子合并类套路） **题目** 在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 试设计出一个算法,计算出将 $N$ 堆石子合 ......
期望DP
### 期望的线性性 即$E(x+y)=E(x)+E(y)$ 期望的其它性质($C$是常数) $$ E(C)=c\\ E(Cx)=CE(x)\\ \text{当X与Y互相独立},E(xy)=E(x)E(y) $$ ### 路径长度 （倒推与期望的线性性） **题目** 给定一个起点为$1$,终点为$ ......
计数dp
### 错位排列计数 （组合意义dp） **题目** 给定长度为 $n$ 的排列,求解其错位排列数 **题解** 设 $D_n$ 表示长度为 $n$ 的排列的错排数,考虑我们已经知道了前 $n-1$ 个错排数,那么对新加入的这第 $n$ 个数进行分类讨论 + 直接与前面的数交换,有 $(n-1)\t ......
斜率优化dp
### 斜率优化简介 **问题引入** 给定一个长度为 $n$ 的序列 $a[i]$ ,连续若干个数可以分为一组,将这些数分成若干组,每一组的代价为组内元素和的平方,要求最小化代价 $n\le 2\times 10^5$ **朴素算法** 设 $f[i]$ 表示将前 $i$ 个数分组之后的最小代价, ......
矩阵快速幂优化dp
### 寻址连续优化 ~~~cpp for(int i = 1; i <= n; i++) for(int k = 1; k <= n; k++) if(a.a[i][k]) for(int j = 1; j <= n; j++) c.a[i][j] = (c.a[i][j] + 1ll * a.a ......
决策单调性优化dp
### 四边形不等式 **定义** 若函数 $w(x,y)(\mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z})$ 对于 $\forall a,b,c,d \in \mathbb{Z}$ ,其中 $a \leq b \leq c \leq d$ , ......
数据结构优化dp
### 滚动数组 在dp时经常会发现只有相邻阶段间状态才会有直接联系,在转移方程中的体现形如：只有前 $m$ 个阶段能影响当前阶段的状态,因此我们不需要储存下 $n$ 个阶段的所有状态,只需要储存 $m$ 个阶段的状态,以做到优化存储空间的目的。 用这种方法可以将dp某一维干掉,把 $\mathca ......
DP技巧与DP杂题
### DP常用技巧 1. 增加维数 2. 交换答案与状态 3. 可行解转最优解 4. 删掉本质相同的状态 5. 对部分状态$dp$ 6. 遇到转移顺序的困难,考虑记忆化搜索 7. 遇到转移细节过多的问题,考虑从 $i\rightarrow i+1$ 而不是 $i-1\rightarrow i$ 8 ......