dfs dp
7.17~7.18 DP专场
#### [CF1814E Chain Chips](https://www.luogu.com.cn/problem/CF1814E) 好久没写这种题了~~ 不带修时，为了让总距离和最短，考虑让相邻的车互换位置，但如果单纯这样有可能剩下一辆车，那就让相邻的三辆车换一下。发现当车的个数 $x \ge ......
DP
# DP 心得总结 ## DP 初步 **dp** 难在思考，状态转移方程最为重要，我们要认真思考，将整个思路变为状态转移方程。 ## 背包 最简单的 **dp** ，要知道背包的状态，背包中所存储，背包中的空间的缩小也是很重要的，我们也要尽量把多维缩小，优化时间复杂度可以更好的实现代码。 ......
7/17dp复健
## 7/17 ### [Valid Bitonic Permutations ](https://www.luogu.com.cn/problem/CF1763D) ### 题意： **构建一个以 $k (2 \le k \le n-1)$ 为峰值的单峰序列 $a$ ，使得在 $i,j$ 位置上的 ......
dfs优化剪枝
题目链接：D - Peaceful Teams (atcoder.jp) 先看数据范围，肯定是搜索相关 首先想到从第1个人， 第0个队开始的搜索顺序 ，因为这属于内部顺序，所以每次搜索要回溯状态，注意要进行大量剪枝 #include<bits/stdc++.h> using namespace st ......
洛谷 P2458 [SDOI2006] 保安站岗 - 树形DP
# [P2458 保安站岗](https://www.luogu.com.cn/problem/P2458) **思路：** 树形DP 三个状态： - dp[i][0]：节点 i 位置放保安的最小花费 - dp[i][1]：节点 i 位置不放保安，但被子节点的保安看守 - dp[i][2]：节点 i ......
DP们
### [CF1763D Valid Bitonic Permutations](https://www.luogu.com.cn/problem/CF1763D) 巨大多分类讨论。枚举 $n$ 的位置 $k$，分以下几类（默认 $iy$ - $k=i,x=n$ - $k>j,x<y$ - $k=j ......
CS5212/CS5202 DP转VGA芯片设计方案
CS5212内置MCU控制器,超低待机功率<100uW，用于设计DP端口到VGA转换器，也可以用于主板DP转VGA方案 ， CS5212AN芯片功能特性： 2-lane通道VESA DP1.1兼容接收机 VGA输出接口，DAC速度高达210MHz，8位 分辨率高达1920x1200x60（RB，缩小 ......
[P5228 [AHOI2013] 找硬币]题解-DP
20230718 [传送门](https://www.luogu.com.cn/problem/P5228 "传送门") 发现$a_i$和$n$都很小 也就是说我的面值最大是$10^5$ 这样最大面值就可以用来做下标 其实最开始也不知道怎么做 我们现在考虑dp $dp[i]$表示最大面值为$i$时的 ......
CDQ分治的优化dp理解
## CDQ分治进阶：优化dp [toc] 蒟蒻做起来非常的蒙蔽 为什么蒙蔽呢？ 因为我没有深刻了解CDQ分治 ### 对于CDQ的深层了解 对于基础的CDQ，我的顺序是可以改变的。 什么顺序：众所周知，CDQ分治分为分治和计算两个部分，这个顺序就是指先分治左右两侧还是先计算中间有mid隔阂的 但是 ......
决策单调性优化DP 学习笔记 & P4767 [IOI2000] 邮局 题解
## 0. 题面 ### 题目描述 高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。 邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和 ......
【动态规划】动态规划基础、背包 dp 学习笔记
# 动态规划基础概念 动态规划（Dynamic Programming，dp）是一类用来解决最优化问题（和部分计数问题）的算法。动态规划的学习和题目从普及组到 IOI 都会出现。 ## 动态规划可解问题的特点 如果一个问题可以通过动态规划求解，则这个问题一定（充分不必要）满足这两个特点： ### 最 ......
调题时出现的问题 in 『状压dp』
# [Luogu P2831 愤怒的小鸟](https://www.luogu.com.cn/problem/P2831 "Luogu P2831 愤怒的小鸟") 考虑 $lowbit[i]$ 的取值范围有可能大于 $18$ 。 ......
「数形结合」- 斜率优化 DP
下面用例题来具体阐释斜率优化的思想。 ## 例 1：[P2365](https://www.luogu.com.cn/problem/P2365) 任务安排 题目大意：有 $n$ 个任务要在一台机器上一次完成。 ......
DP的优化
## [P3287 [SCOI2014] 方伯伯的玉米田](https://www.luogu.com.cn/problem/P3287) 首先容易分析出一个性质：拔高玉米时，拔高 $[i,n]$ 区间的玉米一定是最优的。然后就有了一个暴力DP： 设 $f[i][j]$ 表示对于前 $i$ 个玉米（ ......
abc310f <dp + bitmask>
### 题目 [F - Make 10 Again](https://atcoder.jp/contests/abc310/tasks/abc310_f) ### 思路 [参考](https://www.cnblogs.com/legendstane/p/freee-programming-cont ......
abc310e <公式递推(dp?)>
### 题目 [E - NAND repeatedly](https://atcoder.jp/contests/abc310/tasks/abc310_e) ### 思路  **参考:** https://www.cnblogs.com/legendstane/p/freee-programming-contest ......
【DP】01背包与完全背包总结及空间优化
#### 01背包问题 `题目描述`：有n件物品，每件物品的重量为w[i]，价值为c[i]。现在有一个容量为V的背包，问怎么选取物品放入背包，能使得背包内的总价值最大。其中每件物品只能放入一次。 `样例`： ``` n = 5, V =8 w[i] = 3, 5, 1, 2, 2 c[i] ......
关于 dp 套 dp 的一些思考--zhengjun
dp 套 dp 一般有三种形式： - 暴力搜出一种东西的状态，发现数量不大，建出自动机开始跑； - 有关字符串的匹配问题，例如 kmp 或 AC 自动机上； - 有关 LIS 问题的可以使用一种特殊的内层 dp 优化状态。 前两个没什么好讲的，讲一下第三个。 记 $f_i$ 为 $1\sim i$ ......
BFS和DFS基础
# BFS和DFS基础 ## 搜索简介 搜索是"暴力法"算法的具体实现，是一种吧所有可能的情况都罗列出来，然后逐一检查，从中找到答案的方法。 ### 一般步骤 1. 找到所有可能的数据，并且永数据结构表示和存储。 2. 优化：尽量多的排除不符合条件的数据，以减少搜索空间。 3. 用某个算法快速检索这 ......
从数字三角形开始的DP生活——第二天
[题目链接]("https://www.luogu.com.cn/problem/P1048")  ```c++ #include #include using namesp ......
击杀黄金蛋糕人马（dfs + 记忆化搜索）（难）
题解： 这段代码实现了一个递归的记忆化搜索算法，用于解决一个求最大蛋糕面积下限的问题。下面解释一下其递归思路： 定义状态 设 ways[w][h][m] 表示当前蛋糕的宽度为 w，高度为 h，已经切了 m 刀时，最大蛋糕面积的下限。 状态转移 对于当前的蛋糕，可以选择竖着切一刀或者横着切一刀。竖着切 ......
Codeforces Round 881 (Div. 3) D - Apple Tree（dfs）
https://codeforces.com/contest/1843/problem/D ``` 题目大意： 一颗树中，每次给定两个结点，每个结点都可以移动到孩子结点，最后可以到达叶子结点， 问我们这两个结点最终移到叶子结点有多少种组合？ （其实就是让求以这两个节点为根的子树的叶子结点个数的乘积） ......
abc082d <bitset 状压dp>
### 题目 [D - FT Robot](https://atcoder.jp/contests/abc082/tasks/arc087_b) ### 思路 - 动态规划的方式记录每次行动后, 机器人在坐标系中所有可能位置 - 通过bitset对状态进行压缩, 即每个位置有机器人true or 没 ......
7.14 海高集训 DP 专题 2
## 出题人：$\text{D}\color{red}\text{eaphetS}$ ## [#A. [NOIP2012 提高组] 开车旅行](https://oj.hailiangedu.com/d/hlxly2022/p/P1081?tid=64b026672723396d9906d050) 倍 ......
ABC222D-Between Two Arrays(前缀和优化dp）
题意：给定两个递增数列A和B，构造一个ai <= ci <= bi 的递增数列C，询问满足条件的C的个数。 普通dp会超时，用前缀和优化 n=int(input()) a=list(map(int,input().split())) b=list(map(int,input().split())) ......
DP 做题记录
title: DP 做题记录 mathjax: true date: 2022-07-11 11:04:01 tags: - 四边形不等式 - 线段树 - 左偏树 - 堆 - DP feature: false categories: 做题记录 cover: https://pic.imgdb.cn ......
CF1336C(挺重要的区间dp)
Kaavi and Magic Spell - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 我们直接考虑如何构造出来的字符串，这个字符串显然只能每次最左端加或者最右端加入。 对于第一个字符，显然每个位置都够能放置，且有两种方案。接着下一个字符加入它的左端或者右端，依次类推。 令 d ......
动态DP
title: 动态DP feature: false mathjax: true date: 2022-09-05 16:29:04 tags: - DP categories: 算法 cover: https://pic.imgdb.cn/item/6315fe5316f2c2beb1b5c98f ......