斜率dp
【ACM专项练习#03】打印图形、栈的合法性、链表操作、dp实例
### 运营商活动 #### 题目描述 小明每天的话费是1元，运营商做活动，手机每充值K元就可以获赠1元，一开始小明充值M元，问最多可以用多少天？ 注意赠送的话费也可以参与到奖励规则中 #### 输入 输入包括多个测试实例。每个测试实例包括2个整数M，K（2 using namespace std; ......
dp优化
# dp ## 数位dp ### 模板 ```cpp //下标从1开始统计 初始化均1开始 ll dfs(int pos,int pre_num,int c,int flag) { int max_number; if(pos=0; i--) { if(a[i]>='0'&&a[i] que;//维 ......
ESF、Z-projection和M2DP论文阅读
## ESF ### Title标题 【2011 [ICRB](https://ieeexplore.ieee.org/document/6181760/)】ESF：Ensemble of Shape Functions for 3D Object Classification. 【[code](h ......
[刷题笔记][算法模型总结] Luogu P1880 [NOI1995] 石子合并 || 区间dp之合并石子模型
[Problem](https://www.luogu.com.cn/problem/P1880) ### Solution 本题还有一个弱化版，见[Luogu P1775](https://www.luogu.com.cn/problem/P1775) 我们发现本题和弱化版唯一区别就是本题有环。 ......
#轮廓线dp#HDU 1400 Mondriaan's Dream
[题目传送门](https://acm.hdu.edu.cn/showproblem.php?pid=1400) # 分析 状压dp会TLE，考虑用轮廓线dp， 设 $dp[i][j][S]$ 表示现在处理到 $(i,j)$ 这个位置轮廓线上状态为 $S$ 的情况 二进制位为1表示左边或者上方有骨牌 ......
[算法学习笔记] [算法总结] dp背包模型
### 前言 dp背包模型属dp的一种，可以帮助我们快速的转移状态，解题。dp背包模型题的关键是判断这是哪种背包，属于什么类型的dp，只有判断出这是什么类型的背包，才能进一步朝这个方向思考。 ### 01背包 01背包的常规形式是有$n$种物品，每间物品都有重量和价值两个参数。每件物品都可以选or不 ......
[解题报告] 2023.8.2 dp专题练习赛
比赛链接：[Link](https://www.luogu.com.cn/training/351432#information) [团队私有] T1：[https://www.cnblogs.com/SXqwq/p/17600671.html](https://www.cnblogs.com/SX ......
nefu-dp1 （线性dp）
# nefu-dp1 https://vjudge.csgrandeur.cn/contest/571200#overview 感谢z神的题单 dp废物来打基础了。 (感觉难度大概是递减的) ## 琪露诺 单调队列优化dp ```CC #include using namespace std; co ......
8.2 day9图论+dp
100+70+70+20=260 感觉如果时间够感觉还能写一下，结果T3超大数据结构写死了 T1 观察到最短路径仍然最优，直接dij即可，注意判断终点不用等红灯 T2 暴力是$O(n^4)$的，是dp，但是我写的是分层图，同样时间，还没有优化空间，寄 设计$dp_{i,j}$为跳到$(i,j)$所需 ......
【学习笔记】数位 dp
**数位 dp** 前置知识： * [记忆化搜索](https://www.cnblogs.com/sonnety-v0cali0d-kksk/p/17596911.html) * 五大基础 dp [oi-wiki](https://oi-wiki.org/dp/number/) ## 概念： 数位 ......
我要开始做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电缆适配器寄存 ......
斜率优化
# part 1 引入 ### 一.斜率优化的作用 在一个dp中，往往转移一个状态与很多状态相关，每一次转移都扫一遍与它相关的状态浪费了很多时间。但总有一些状态无法转移到它之后的状态，这时考虑转移它们就没有意义。我们用一些数据结构来维护有意义的状态从而节省时间。 ### 二.斜率优化的使用限制 1. ......
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) 现在考虑某一局面。 此 ......