概率dp

对于一个概率 \(p\)，设它能提供的期望值为命中此概率的次数。那么保持这个概率直至命中此概率的期望值为 \(\frac{1}{p}\) 证明： \[\begin{aligned} \sum\limits_{i = 1}^{\infty} (1 - p) ^ {i - 1} * p * i &= p ......

颜色的长度 Color Length 题面翻译 输入两个长度分别是 $n$ 和 $m(n,m\leq 5000)$ 的颜色序列，要求按顺序合并成同一个序列，即每次可以把一个序列开头的颜色放到新序列的尾部。 例如，两个颜色序列 GBBY 和 YRRGB，至少有两种合并结果：GBYBRYRGB 和 YR ......

数数与dp CF294C Shaass and Lights 记被分成的 \(m+1\) 段每一段的长度为 \(l_i\) 答案为 \[\frac{(n-m)!}{\prod\limits_{i=1}^{m+1}l_i!}\times \prod\limits_{i=1}^{m+1}2^{l_i-1 ......

DP无思路题汇总 即只能完全靠题解想出做法的题目。 P5020 NOIP2018 提高组 货币系统 P2851 USACO06DEC The Fewest Coins G ......

NFLSOJ A CF294C Shaass and Light 考虑初始已点亮的灯将所有剩下的灯划分成的连续段。除开头结尾外，每个长为 \(l\) 的连续段有 \(2 ^ l\) 种操作序列。开头结尾的连续段只有 \(1\) 种操作序列。从前往后将所有的操作序列归并到全局的操作序列里，拿组合数随便 ......

一. 随机事件与概率 1.1 随机现象 在自然界和人类活动中，发生的现象多种多样，比如下列这些现象： 1. 偶数能被2整除 2. 光的速度是常数 3. 一家门店一天之内的订单量 4. 一个新生儿可能是男生也可能是女生 5. AB实验存在对照组和实验组 6. 李华上厕所的时间 不难发现，其中①②⑤这类 ......

1.这里密度比较抽象，可以理解成高度，更直观 f(x,y)可以理解成一个区域中某一点的高度，那f(x,y)的二重积分就是这个区域*对应的高度=体积 关于 边缘概率密度，实际是一个截面的面积，和高度不一样了。 fx(x)指对x的边缘密度，意义是垂直x轴切片，给一个x，输出x处的截面积 fy(y)指对y ......

题目 求方案数，考虑 dp —— 状态设计和边界 —— 题目告诉了一个很显然的性质： 每一排从左至右保证高度单调递减 每一列从后往前保证高度单调递减 那么可以发现，对于每一行，每一列，一定是按高度顺序插入，并且是连续插入，因为如果不连续，就无法保证单调递减的性质 同时，它给出了另一个性质 ： \(N ......

DP练!习! 都是水题啊 Made By M1kuFan 1 洛谷 P2513 求长度为 \(n\) ，逆序对个数为 \(K\) 的排列有多少个，答案对 \(1e9 + 7\) 取模 其中：\(1 \le n,K\le100\) 仅考虑从大到小向序列中插入每个数的位置，当前插入到了第 \(i\) 个 ......

随机变量与分布函数 随机变量本质上就是个变量，它分为两种：连续型随机变量（变量的可能取值是连续的，比如小酱等车的时间没法精确到准确的值）和离散型随机变量（变量的可能取值是离散的，比如小酱扔硬币只有正反面两种值）。 分布函数的定义：假如 \(X\) 是个随机变量，那么它的分布函数 \(F(x)\) 被 ......

清醒了一点后我又写了一道黄色DP题，做出来了，还行，开心不少了... 中途暴露出一些问题 1、深搜过程中既然用了二维数组，那么深搜时就应该用二维循环取最优解，而不是只从最后一行中进行一维循环取最优解。 2、dfs递归的过程中应该用dfs！！！不应该像个智障一样的忘了用dfs，直接用dp数组忘了递归了 ......

这道题好几天前就写出了记搜代码，但是理论上空间恰好够，实际上不论是用new-delete还是malloc-free，都有1~2个点MLE了（最抽象的是一开始MLE两个点，我把数组两个下标调换顺序后理应得到相同的分数，但实际上...竟然变成只MLE一个点了...离谱至极），看来动态内存不是那么好使，他 ......

P1220 关路灯 很典的一道题，但是以前居然不知道。 数据范围很小，可以直接搜索通过，加一些奇奇怪怪的贪心策略和剪枝即可和正解差不多速度通过。 \(Code_violent\) ll ans=9e18; int n,st,loc[51],p[51]; void dfs(int x,ll t,ll ......

还在更新ing 一、引入 在动态规划状态设计中，若状态是一个集合，例如 \(S=\) { \(1,0,1,1,0\) } ，则表示第 \(1、2、4\) 个节点被选中（从右往左对应 \(0 \sim 4\) 号节点）。若集合的大小不超过 \(N\) ，则集合中的每个元素都是小于 \(K\) 的正整数 ......

还在更新ing 前言 此乃小 Oler 的一篇小小算法随笔，从今日后，还会进行详细的修订。 一、简单介绍（change root dp） 如需了解树形dp的，本蒟蒻毛遂自荐，万字大文动态规划【树形dp】Tree DP ~~~详解 换根dp，又叫二次扫描，是树形DP的一种，是一种用来求解树上各点到其他 ......

石子合并 别人讲过太多了，蒟蒻就不说了。 Polygon 这题跟石子合并类似，只是多输出了个先清除哪条边可以使得值最大。 因为我们不确定先删那一条，我们就再复制一遍添到输入的结尾，就变成了 $2 \times N - 1$。 我们思考最大值是由哪些贡献的。 最大值与最大值运算。 最小值乘上最小值（因 ......

关于状态表示形式的优化方式。 使用场景：需要记录不超过二进制数位(通常22位以内)的bool信息的DP问题。 常见的位操作 简单操作 任何二进制数位 &1 得到它本身。 任何二进制数位 ^1 则取反。 任何二进制数位 &0 则赋值为0。 任何二进制数位 |1 则赋值为1。 混合操作 (n>>k&1) ......

[USACO23OPEN] Pareidolia S 对于这种题，两种思路，一种是直接 \(dp\)，一种是考虑每个 bessie 产生的贡献。 显然直接考虑 bessie 产生的贡献难以解决 bbessie 的情况，所以考虑 \(dp\)。 设 \(f_{i}\) 表示以 \(i\) 开头的字符串 ......

CF566F $1500$ 容易考虑到 $n^2$ 做法：设 $dp_i$ 为第 $i$ 个数选的答案，对于排好序的序列，枚举前面的数 $a_j$，如果 $a_j|a_i$ 就转移，时间复杂度易知 $O(n^2+n\log n)$。 由于 $a$ 至于很小，延续刚才的思路，设 $dp_i$ 为选值为 ......

1.又是一道因为写了异常剪枝而调了好久的题，以后再也不写异常剪枝了，异常情况压根不该出现，所以针对出现的异常情况进行补救的异常剪枝是一种很容易出错的行为，做为两手准备也就罢了，但第一次写成的代码必须能在没有异常剪枝的情况下算出正确结果才行！ 2.还提出了一个专门针对记搜的编码规范：编写记忆化搜索的时 ......

这道题让我更深入的理解了记忆化搜索的过程，既然记忆化搜索的结果要靠返回值来传递，那么记忆化搜索解决问题的必须是倒序的，即记忆化搜索是一个简化问题倒序解决的过程，普通搜索是一个复杂化问题逐步尝试并记录尝试结果的过程。 特别是对于求总种数的记忆化搜索，就是把能干的事情组合起来然后把情况全都加到DFS变量 ......

在这道题中，我第一次用了memset，确实方便，不过需要注意的是只有全部赋值-1和0的时候才能使用它，否则他能干出吓死人的事。以及memset在cstring头文件里，在本地就算不include也能照常编译，但评测机里可能不行，所以一定要写上cstring 同时，我半获得半自我总结了一个暴论，这个暴 ......

那些分布 二项分布 泊松分布 几何分布 帕斯卡分布 均匀分布 指数分布 正态分布 它们的参数、概率密度函数与分布函数、统计特征、意义 那些公式 期望 \[E(g(X))=\int_{-\infty}^{+\infty}g(t)f(t)dt. \]密度函数 \(y=g(x)\)处处可导且严格单调，则： ......

DP查缺补漏之多重背包优化原理 普通思路 类似完全背包 for(int i=1;i<=n;i++) for(int j=1;j<=V;j++) for(int k=1;k<=V/c[i];k++) { if(k*c[i]<=j) f[i][j]=max(f[i-1][j],f[i-1][j-k*c[ ......

Mondriaan's Dream Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 29096 Accepted: 15505 Description Squares and rectangles fascinated the f ......

DP查缺补漏之完全背包优化原理 先复习一下基本知识 状态假设 DP[I][J]为前\(i\)个物品，容量小于\(j\)时的最优解（最大价值） 状态转移 DP[I][J] = max(DP[I - 1][J], DP[I - 1][J - k*V[I]] + k*W[I]) 对于第\(i\)个物品，两 ......

Chocolate Bar 我们看到 \(n,m\le 30\) 想到暴搜。 考虑枚举分割线，一直到刚好满足需要或者只有一个巧克力的情况。 随手跑了个最优解。 inline int dfs(int n,int m,int k){ if(n*m==k)return 0; if(k<=0)return ......

DP查缺补漏之01背包优化原理 先复习一下基本知识 状态假设 DP[I][J]为前\(i\)个物品，容量小于\(j\)时的最优解（最大价值） 状态转移 DP[I][J] = max(DP[I - 1][J], DP[I - 1][J - V[I]] + W[I]) 对于第\(i\)个物品，两种可能 ......

zr模拟赛 8 你好我的朋友，现在我生病了，对不起。 23zr提高day8-测测你的计数水平 👌 首先断环为链，方法是枚举某一个点连的是那一条边。 接着设\(f_i\)表示从左到右扫到i的时候所有区间都没有超过i的方案数。 然后发现如果当前新区间覆盖了两个相同颜色的点就寄了，但是没有就没事。 另外 ......

10.30 ICPC-22-JN C(62/504) dfs的同时DP，u由fa转移，问题在于求同层兄弟选i个组成size和为j的方案数：这个暴力是\(O(n^4)\)的，一开始考虑了预处理前后缀再拼起来，然而拼起来的复杂度更高；想到先所有儿子做一遍再回退DP，但又觉得银牌DP题用不到这么高级的东西 ......