斜率dp
CF Fish(状压dp+记忆化搜索+概率dp)
### 题目描述 n fish, numbered from 1 to n, live in a lake. Every day right one pair of fish meet, and the probability of each other pair meeting is the sa ......
斜率优化
# 斜率优化 ## 大致思想： 将决策点视为若干二维平面上的点，将当前点的已知条件视为斜率，将 $dp_i$ 视为截距。寻找经过某个点且斜率一定的直线的最小截距。（寻找最大截距时需要将 $dp$ 取负，转化为最小，这样维护的凸包就始终是下凸包） ## 凸包的维护： ### 单调队列： 满足条件：满足 ......
P6758 vim 线头 dp 题解
显然，e 在这道题里是无关紧要的。我们知道每删掉一个 e 需要 hx 两步，所以我们把所有的 e 统计出来，标记一下他后面的点（一定要经过后面这个点才能删掉 e），下文中我们叫这些点为关键节点。那么问题就变成了：如何用最少的代价经过所有关键节点。 发现我们最终走过的路径一定是这样的形式：我们 f 到 ......
[算法学习笔记] 0基础带你入门dp
### 前置知识 在学习dp前，你可能需要掌握: - dfs - 搜索及剪枝技巧 - 记忆化搜索 ### 引子 我们从一个经典例题开始入门： > 一只青蛙跳楼梯，一次可以一级或两级，若青蛙想要跳 $n$ 级楼梯，有多少种跳法？ 我们可以很容易想到暴力dfs，每次dfs跳一级和跳两级，跳到$n$ 级后 ......
P1002 [NOIP2002 普及组] 过河卒 入门级别的dp
思路： 1.标记马点 z[i][[j]=0 2.正常 z[i][j]=z[i-1][j]+z[i][j-1] #include<iostream> using namespace std; int n,m,a,b; long long ma[30][30],bck[30][30]; int dx[8 ......
【学习笔记】空空的浅谈DP
> 特邀讲师：墨染空 洛谷用户@[Remake](https://www.luogu.com.cn/user/161687) # DP ## 1 决策单调性 ### 1.2 由已知量转移：分治算法 > - [ ] [洛谷 P3515： [POI2011] Lightning Conductor](h ......
期望概率DP
## 期望的线性性 > > >![image-20230711140132449](http ......
单调栈与单调队列优化 dp
## 单调栈 将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。 例如，栈中自顶向下的元素为 $\{0,11,45,81\}$。 ![image](https://img2023.cnblogs.com/blog/2618414/202 ......
【做题笔记】线性dp——线段树优化
**线段树优化是用来对于$DP$数组区间赋值的。** 主要是区间取最值 来优化线性dp 真没什么可写的了 挂两个题目： [P4644 [USACO05DEC] Cleaning Shifts S](https://www.luogu.com.cn/problem/P4644 "P4644 [USAC ......
D. Bag of mice -- （概率Dp）codeforces 148
###原题链接：[https://codeforces.com/contest/148/submission/213227373](https://codeforces.com/contest/148/submission/213227373) ###题意：捉老鼠游戏，谁捉到白鼠就是胜利，我们求公主 ......
E. Two Chess Pieces -- （codeforces) 树形DP
###原题链接：[https://codeforces.com/contest/1774/problem/E](https://codeforces.com/contest/1774/problem/E) ###题意：两颗棋子，给出两颗棋子必须要去的顶点，且给出两颗棋子的相隔距离不能大于d，算出两颗 ......
Apple Tree(树状搜索,树形DP)
Apple Tree time limit per test 4 seconds memory limit per test 512 megabytes input standard input output standard output Timofey has an apple tree gro ......
abc076d <dp / 贪心>
[D - AtCoder Express](https://atcoder.jp/contests/abc076/tasks/abc076_d) ``` // https://atcoder.jp/contests/abc076/tasks/abc076_d // // dp[i][j] 表示第i秒 ......
【计数，DP】CF1081G Mergesort Strikes Back
[Problem Link](https://codeforces.com/contest/1081/problem/G) 现有一归并排序算法，但是算法很天才，设了个递归深度上限，如果递归深度到达 $k$ 则立即返回。其它部分都和正常归并排序一样，递归中点是 $\lfloor (l+r)/2 \rf ......
CF1585F Non-equal Neighbours - 容斥 - dp - 单调栈
题目链接：https://codeforces.com/problemset/problem/1585/F 题解： 难难难 考虑容斥：设 $A_i$ 表示 $b_i \neq b_{i+1}$ ($i=1,2,\cdots,n-1$) 时对应的 $\{b_i\}$ 方案的答案 那么答案就是 $$\b ......
斜率优化dp学习笔记
title: 斜率优化dp学习笔记 date: 2023-06-27 09:06:47 tags: 学习笔记 cover: https://i.imgloc.com/2023/06/27/VNgMYQ.jpeg # 前置知识 单调队列优化 dp，计算几何基础知识，小学数学。 # 斜率优化 在 dp ......
【计数，DP】ABC306Ex Balance Scale
[Problem Link](https://atcoder.jp/contests/abc306/tasks/abc306_h) 现在有 $n$ 个球，每个球有一个重量，重量未知。接下来会进行 $m$ 次称重，每次给定 $a_i$ 和 $b_i$，比较这两个球的重量，结果可能是 $>,=, 点击查 ......
ETHERNET/IP转PROFIBUS-DP网关PROFIBUS DP/ EtherNet IP网关
大家好，今天要给大家介绍一款非常神奇的通讯网关捷米特JM-DPM-EIP！这款产品可以将各种PROFIBUS-DP从站接入到ETHERNET/IP网络中，真是一款神奇的产品啊！你是否想过，如果没有这款产品，PROFIBUS-DP从站和ETHERNET/IP网络之间该怎么通讯呢？让我们来看看这款产品到... ......
2023ACM暑假训练day 4 简单DP
[toc] # DAY 4 简单DP ## 训练情况简介 简单DP时间安排：6.29 - 6.29 早上：过A题 下午：过B、I、K、L、N题 晚上：补个人训练2的E题、F题 ## A 题 **题意：** 从长为n的数组取m个序列，求这m个序列的最大和 **思路：** //Max[j-1]目前代表的 ......
<DP>总结
# DP总结 ## 常规DP ### [[USACO1.5] [IOI1994]数字三角形 Number Triangles](https://www.luogu.com.cn/problem/P1216) #### 解题思路 **对于到达（i，j）点时的最大值，其状态仅由（i-1,j）和（i-1, ......
树上dp
树上dp ##### 树的存储 邻接表：将这个点的所有直接子节点存储在以这个点为开头的链表上 https://oi-wiki.org/graph/save/#%E9%82%BB%E6%8E%A5%E8%A1%A8 ```cpp void add(int u,int v)// 添加一条边u->v { ......
CF1842E Tenzing and Triangle - 线段树优化 dp -
题目链接：https://codeforces.com/contest/1842/problem/E 题解： 首先，如果两个等腰三角形相交了，那答案肯定不会更优。因此不会相交。 先考虑一个 $n^2$ 的 dp： 设 $dp_i$ 表示考虑到 $x=i$ 时的最小代价，首先可以先都加一个 $\sum ......
概率/期望dp刷题整理
## [Bag of mice](https://codeforces.com/problemset/problem/148/D) 题意：有w只白鼠和b只黑鼠，公主和龙轮流抓老鼠，其中龙每抓一只老鼠就会有一只未被抓住的老鼠逃走，先抓到一只白鼠的获胜，问公主获胜的概率是多少 ### Solution ......
230706 // 换根 DP 复习
菌：园什是我笋子 元首：我是你打野 我：元首耳朵得治 ### G. 求树的重心 http://222.180.160.110:1024/contest/3744/problem/7 我们知道，重心的定义是，将其切除后，每个连通块的大小不超过 $\dfrac n2$。连通块分为 *其子树* 和 *整棵 ......
斜率优化 DP
### 前置知识 - [凸包及求法](https://www.cnblogs.com/TKXZ133/p/17529525.html) - [李超线段树](https://www.cnblogs.com/TKXZ133/p/17529789.html) - *CDQ 分治与平衡树 ## 斜率优化 # ......
DP 优化
## 1. 单调队列优化 DP ### 1.1 简介 **当一个选手比你小还比你强，你就打不过他了。**这是对单调队列简单形象的概括。 单调队列在转移的过程中不断**排除不可能成为决策点的元素**，使每次转移寻找决策点的时间复杂度降为 $O(1)$。一般地，可被单调队列优化的转移式可被写为如下形式： ......
浅谈斜率优化
如果一个 DP 的转移方程可以写成 $f_i=\underset{j\{f_j+a_i\times b_j+c_i+d_j\}$ 的形式，那么可以运用斜率优化。 不妨设转移是 $\min$，设 $g_{i,j}=f_j+a_i\times b_j+c_i+d_j$，即 $f_i=\min\limit ......
DP优化
# 优化DP笔记 ## [P6040 「ACOI2020」课后期末考试滑溜滑溜补习班](https://www.luogu.com.cn/problem/P6040?contestId=116096) 设 $f_i$ 表示老师解决到第 $i$ 个学生需要最少的精力，答案显然是 $f_n$ 边界 : ......
2022-09-15-概率期望 DP 消除后效性的相关总结
abbrlink: '' categories: [] date: '2022-09-15' tags: - 数学 title: 2022-09-15-「Note」概率期望 DP 消除后效性的相关总结 toc: true updated: '2022-09-15 19:03:03' 或许这个 `tr ......