概率 记忆fish dp

回忆笔者学习动态规划的时候，最开始接触的是经典的 “01背包” 问题；不过现在想起来，以“01背包问题”作为初次接触的动态规划算法的问题_并不友好_；花费了不少时间才慢慢感悟到动态规划算法的核心思想。先前的文章中涉及了不少搜索算法，在搜索算法上融入动态规划算法思想的 ......

本题我们采用隔板法+容斥原理来解决 合格总方案数 = 总方案书 - 不合理的方案数 = 不考虑limit的方案数 - 不合法方案数（至少有一个小朋友 > limit） 任意方案数 n个小球放到3个盒子中 -> n + 2个位置，选两个位置放隔板剩下位置放球 c(n + 2, 2) 三个小朋友为：甲乙 ......

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[101 ......

概率论 参考：https://zhuanlan.zhihu.com/p/330669300 简介 被期望坑过无数次了。痛定思痛，决定写一写。OI中期望常可以通过线性递推得到状态转移，所以也有很大一部分期望题因此被冠以 “期望/概率DP” 之称，属于广义的 “动态规划” 范畴。当然，OI中涉及的大多是 ......

昨天好几道题没做出来很郁闷，结果今天上来半小时不到就直接做出一道黄DP题了，不错，又有写题的冲动了。 这道题我一直被那个“因为方案数可能很多，请输出方案数对 1000007取模的结果。”这句话吓到了，因为我在想如果涉及求最优方案，那么势必会有比较，那么既然取了摸还怎么比较啊？不会另要开一个数组记录每 ......

一.定义 即对于一个区间进行的dp 二.经典转移方程 1.枚举断点型 f[l][r]=min(f[l][k-1],f[k][r]) (l+1<=k<=r) 2.左右端点型 f[l][r]=min(f[l][r-1],f[l+1][r]) 3.有一定条件型 f[l][r][k]=f[l][r-1][k ......

一.定义 树形dp，顾名思义，即为树上的DP。 二.分类 1.普通树形dp 2.换根dp 三.一些常用技巧及思想 1.补集转化思想：就是数学常用的“正难则反”。 例：一棵树，每个点有权值，要求选一个连通块，此连通块包含最大权值的方案数。 解:将包含最大权值的连通块个数转化为所有连通块个数减去不包含最 ......

使用场景 状态 \(O(n)\)，转移 \(O(n)\)，只涉及 \(i,j\) 两个未知量，\(j\) 的取值范围的左、右端单调，可以把 \(f_i\) 当做截距维护上（max）、下（min）凸包。需要注意的是，它作用不仅仅可以优化 DP，本质是求某些最值，\(\color{red}\text{e ......

状态设计 由于具有更改操作，我们希望更改后会变的东西可以简单的通过线段树上单点修改来维护。 对于一般的常数层转移 DP，这一点较好处理。但是对于树上 DP，就需要结合重儿子进行设计另一个 \(g\) 数组，表示不含重儿子的 DP 值，就可以结合树剖快速计算。 如这道，各点有不同代价，可覆盖子树所有叶 ......

我是链接 一眼状压DP，选出一些a从前往后塞，f[i][j]表示选出的a状态为i，且结尾为j时最小花费 转移就看上一个状态结尾和当前结尾在a里的下标是否顺着挨着，不是顺着挨着就要加个c 这样会tle #include<bits/stdc++.h> #define int long long usin ......

对于这道题可以很容易写出状态转移方程。但直接转移会超时，所以需要单调队列优化。这里的单调队列采取左闭右开写法，容易理解。 怎么做呢？常规取出队头决策就不多说了。怎么判断当前决策是否更优呢？当状态较优秀且树高比较高，就可以考虑去掉尾巴。 代码： #include <bits/stdc++.h> #de ......

蒟蒻DP太菜了QAQ。 一点体会：DP就是如何通过最少的信息确定最优解。 P5664 [CSP-S2019] Emiya 家今天的饭 思考了一下，发现第3个要求很难直接搞，于是考虑正难则反，用总方案数减去不符合要求的方案数。求总方案数： \(g_{i,j}\) 表示在前 \(i\) 行中选 \(j\ ......

想搜索到最后一层，就必得先完成前面层的搜索任务，这构成了对状态转移的启示，即当前层的DP值应该是此前层转移过来后得到的最佳值。 但这道题看数据范围应该不能用二维数组，抱着侥幸的心理我使用了动态二维数组，dpij表示以第i层第j个为终点时的答案，结果MLE了，喜提42分，详见CODE-1。 后来意识到 ......

//http://ybt.ssoier.cn:8088/problem_show.php?pid=1302 #include<bits/stdc++.h> using namespace std; const int N=2e5+10; int dp[N][3][3],n,w[N],t; int m ......

Intervals 有 \(m\) 条形如 \((l, r, a)\) 的限制，表示如果 \(s_{[l, r]}\) 中有 1 就会有 \(a\) 的价值。 你要求长度为 \(n\) 的 01 串的价值的最大值。 \(n, m \le 2 \times 10^5\)。 将每个限制挂到右端点上，在右 ......

简介 有一类问题，他们需要计算满足在序列上插入给定顺序的元素，其贡献/限制只与两旁的元素有关，但元素插入的位置是不一定的，所以会有代价的最值和方案数的统计。而对于这类问题，我们其实可以不关心每一次插入的具体位置在哪里，而只关注他的相对位置（比如在某个数左边、在某个数左边且与其相邻之类的），从而将状态 ......

区间 DP 区间 DP 是可以由小区间的结果往两边扩展一位得到大区间的结果，或者由两个小区间的结果可以拼出大区间的结果的一类 DP 问题 往往设 \(dp[i][j]\) 表示处理完 \([i,j]\) 区间得到的答案，按长度从小到大转移 因此一般是先写一层循环从小到大枚举长度 \(len\)，再写 ......

题目描述 定义数字串是好的当且仅当其包含子序列 2017 ，不包含子序列 2016。 定义数字串的丑陋值为最少删掉几个字符，它才能是好的，如果一直不能，就是 \(-1\) 。 给定数字串 \(t\) ，长度为 \(n\) ，\(q\) 次询问求 \([l,r]\) 的丑陋值。 \(1 \leq n, ......

What is fish-scale pits? Fish scales in a semicircular, crescent-shaped pit It is built on a hillside and can often be seen on the slope of the tunnel ......

DP查缺补漏之\(LCS\)状态重叠 状态假设 \(F[i][j]\)为\(a\)串中前\(i\)个字符，\(b\)串中前\(j\)个字符构成的\(LCS\) 状态转移 \(F[i - 1][j - 1] + 1\) 即当且仅当\(a[i] = b[j]\)时，从两个序列的减去当前的字符加一推出 \ ......

DP查缺补漏之\(LIS\)状态记录 前置知识 状态假设 \(F[i]\)为以\(a[i]\)为结尾的最长上升子序列长度。 状态转移 \(F[i] = max(F[j] + 1, F[i]) (j < i)\) 很好理解，即\(i\)之前的所有以\(a[j]\)结尾的最长上升子序列中取最大，再加上\ ......

目录数位DP第一个例题 数位和第二个例题 数数相关资料例题综合运用模板题 数位DP 数位DP用于数字的数位统计，如果题目和数位统计有关，那么可以用数位DP思想，把低位的统计结果记录下来，在高位计算的时候直接使用低位的结果 感觉很抽象啊，而且还有点难啊啊啊。下面给出的几个例题再理解理解！ 数位动态规划 ......

为了更好的阅读体验，请点击这里 题目链接：G - Electric Circuit 看到了 \(N\) 的数据范围，因此是显然的状压 dp。 不妨设 \(f_S\) 为仅使用 \(S\) 集合中的所有点，能够连成恰好 \(1\) 个连通块的方案数。\(g_S\) 为仅使用 \(S\) 集合中的所有点 ......

对于一个概率 \(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 ......