概率dp

换根法思路： 1. 自下而上递推； 2. 自上而下递推。 ### P3478 [POI2008] STA-Station #### 题目描述： ![image](https://img2023.cnblogs.com/blog/2940791/202305/2940791-2023052811190 ......

战绩： 100+80+60+72=312 rk4 T1 感觉作为签到有点难，考场一开始看了20分钟，先开了T2 卡住的原因是注意到异或并不具有结合律和分配律，那么如果我们要直接dp答案，是非常困难的 dp的本质是将相同类信息合并在一起处理 注意到异或最大值不超过128（不进位加法） 于是我们想到将异 ......

## 树形DP——基础 ### P1352 没有上司的舞会 设 $f[i][0/1]$ 表示第 $i$ 个人不去或者去。 如果第 $i$ 个人没去，那么下属可去可不去，所以 $f[i][0] = \sum max\{f[j][0],f[j][1]\}$，$j$ 为 $i$ 的子节点。 如果第 $i$ ......

### [L. Hamiltonian Wall](https://codeforces.com/problemset/problem/1766/C) **算法：**dp **做法：**由于要一笔将所有黑块都划出来。所以我们状态转移方程应尽可能从左上角或者右下角的黑方块转移过来。$$f[i,j] = ......

大家好，今天要给大家介绍一款非常神奇的通讯网关捷米特JM-DPM-EIP！这款产品可以将各种PROFIBUS-DP从站接入到ETHERNET/IP网络中，真是一款神奇的产品啊！你是否想过，如果没有这款产品，PROFIBUS-DP从站和ETHERNET/IP网络之间该怎么通讯呢？让我们来看看这款产品到... ......

ASL北京集睿致远研发CS5218 DP转HDMI 4K 30HZ 转换芯片，支持高达3840 x2160@30Hz 或者4096x2160@30Hz ，主要用于设计TYEPC 拓展坞和DP转接线的开发与应用。CS5218芯片设计电路： CS5218替代LT8611芯片包括2路双模DP电缆适配器寄存 ......

**DP**是OI竞赛中应用**特别广泛**的一类算法 ~~（通常我用来骗分打表）~~ 下面进入正题 ### Part 1.01背包 01背包的题目要求通常是给你一些物品，每个物品有它的重量和价值，你有一定的空间来装这些东西，一种只有一个，问能拿走最多多少价值的物品。就相当于你在逃难中只有一个包，你 ......

一些经典的 DP 类型。 # I.数位 DP 数位 DP 归在此处，无论是高位往低位还是低位往高位。需要注意数位 DP 的本质是一种按位比较的贪心思想，因而可以加以扩展。 ## I.[[CQOI2013]二进制A+B](https://www.luogu.com.cn/problem/P4574) ......

通过某些 trick 以优化复杂度。 # I.单调队列/单调栈 单调队列/单调栈优化 DP 是对简单决策单调性 DP 的常见优化。 ## I.[[HNOI2005]星际贸易](https://www.luogu.com.cn/problem/P2317) 第一问直接背包一下就行，是模板。 然后，因为 ......

DP 时可行的某些套路。 # I.DP 的图论化 将 DP 式子实际化有时会提供新思路。 **这可以被看作是同一个 DP 式解决不同的问题，因此一定程度上考验出题的功夫**。 ## I.[[UOJ#76][UR#6]懒癌](https://uoj.ac/problem/76) 现在考虑某一局面。 此 ......

战绩： 100+100+20+54 = 374 T1 据lxl说是为了成绩好看加的题，难度大概cspjT1 T2 朴素dp然后树状数组优化一下 T3 赛时脑抽链，写了个dp，一直想优化dp，其实贪心就好了，过程更加简洁，优化很显然 先将区间剖分成两段端点$s_i=s_j$相同的多条线段 将区间每个点 ......

## [P3565 [POI2014] HOT-Hotels ](https://www.luogu.com.cn/problem/P3565) ### $solution 1$: 先说一下我想到的 $O(n^2)$ 算法。 首先不难发现，如果三个点两两距离相等，那么一定存在一个中心点，使得中心点到 ......

### P1880 [NOI1995] 石子合并（破环成链+石子合并类套路） **题目** 在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 试设计出一个算法,计算出将 $N$ 堆石子合 ......

### 期望的线性性 即$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的一般套路 **问题形式** 给你一个条件 $A$ ,然后询问值大小在 $[L,R]$ 中有多少满足条件的数 这个问题暴力去做一般是 $\mathcal{O}(R)$ 的时间复杂度,但是通过数位dp我们可以把这个东西优化到 $\mathcal{O}(\log_{10}R)$ **求解 ......

### 错位排列计数 （组合意义dp） **题目** 给定长度为 $n$ 的排列,求解其错位排列数 **题解** 设 $D_n$ 表示长度为 $n$ 的排列的错排数,考虑我们已经知道了前 $n-1$ 个错排数,那么对新加入的这第 $n$ 个数进行分类讨论 + 直接与前面的数交换,有 $(n-1)\t ......

### 斜率优化简介 **问题引入** 给定一个长度为 $n$ 的序列 $a[i]$ ,连续若干个数可以分为一组,将这些数分成若干组,每一组的代价为组内元素和的平方,要求最小化代价 $n\le 2\times 10^5$ **朴素算法** 设 $f[i]$ 表示将前 $i$ 个数分组之后的最小代价, ......

### 寻址连续优化 ~~~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 ......

### 四边形不等式 **定义** 若函数 $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时经常会发现只有相邻阶段间状态才会有直接联系,在转移方程中的体现形如：只有前 $m$ 个阶段能影响当前阶段的状态,因此我们不需要储存下 $n$ 个阶段的所有状态,只需要储存 $m$ 个阶段的状态,以做到优化存储空间的目的。 用这种方法可以将dp某一维干掉,把 $\mathca ......

### DP常用技巧 1. 增加维数 2. 交换答案与状态 3. 可行解转最优解 4. 删掉本质相同的状态 5. 对部分状态$dp$ 6. 遇到转移顺序的困难,考虑记忆化搜索 7. 遇到转移细节过多的问题,考虑从 $i\rightarrow i+1$ 而不是 $i-1\rightarrow i$ 8 ......

### LCS问题 **题目1** 给定 $A,B$ 两个排列,求它们的 $\text{LCS}$ **题解1** 两个序列都是排列,那么可以考虑建立映射关系跑LIS **题目2** 给定 $A,B$ 两个序列,求它们的 $\text{LCS}$ **题解2** 就是个简单的多序列dp 设 $f[i ......

### [BJOI2019] 排兵布阵 （背包dp与贪心） **题目** 小 C 正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第 $i$ 座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。 如果一名 ......

### P3174 [HAOI2009] 毛毛虫 （树的直径变式） **题目** 对于一棵 $N$ $(N \le 3\times 10^5)$ 个点的树，我们可以将某条链和与该链相连的边抽出来，看上去就象成一个毛毛虫。 求点数最多的毛毛虫 **题解** 本题与树的直径的求法非常类似 设 $f_u$ ......

### 相关技巧 + 枚举子集：如果一个集合状态 $S$ 由其所有子集 $S0\subsetneq S$ 转移得到，这样转移的时间复杂度为 $\sum\limits_{i = 0} ^ n\dbinom n i 2 ^ i=3 ^ n$ ~~~cpp for(int S0 = S; S0; S0 = ......

## 动态规划基础知识 ### 基本概念 1. 动态规划：解决**多阶段决策过程最优化**问题的一种方法。 2. 阶段：把问题分解成相互联系的有顺序的几个环节，这些环节即成为阶段。 3. 状态：某一阶段的**出发位置**称为状态。通常一个阶段包含若干状态。 4. 决策：从某阶段的一个状态演变到下一个 ......

**[problem1 一双木棋 chess](https://www.luogu.com.cn/problem/P4363)** 分析性质，发现每个时刻的状态都是锯齿线，考虑怎么把状态压进去，对于每个时刻都对应一个在 n 维上走了若干步和 m 维上走了若干步，如果用一个 11 进制数存的话会有 $ ......

前言： k8s的全称是kubernetes，取头尾的字母中间有8个字母所以简称为k8s，它的诞生是为了解决庞大的集群管理，提供了更为便捷的管理方案；由于k8s是一个庞大的集群管理平台，所以此文只介绍简单的使用方式和一些需要了解的基础感念；在工作中，我们极少可能会自己搭建k8s所以此文也不去接受如何搭 ......

这类问题大概长这样： 求一个排列 $p_{1\sim n}$，最小（大）化如下值： $$ \sum\limits_{i=1}^{n-1}f(p_i,p_{i+1})\\ f(i,j)= \left\{ \begin{array}{**lr**} g(i)+h(j),ij \end{array} \r ......

#include<bits/stdc++.h> using namespace std; int t,m,w[105],v[105],f[105][1005]; int main() { cin>>t>>m; for(int i=1; i<=m; i++) cin>>w[i]>>v[i]; for( ......