zhengjun dp

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 同时，我半获得半自我总结了一个暴论，这个暴 ......

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\)个物品，两种可能 ......

构造题注意事项 一定要转化思路，不要总是盯着一个特殊点； 多注意特殊点的变化： 例如 P7115 [NOIP2020] 移球游戏，如果总是盯着一个全不是 \(c\) 的栈和一个空的栈对其他栈操作，就会使得步数要翻一倍，然而如果只操作一半，那么此时可以用当前栈作为新的空栈，原来的空栈作为新的全不是 \ ......

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题用不到这么高级的东西 ......

D. Pawn 感觉这种dp套路似乎非常常见，我们可以设 f[i][j][x]表示走到(i,j)，当前的值为f[i][j][x]*k+x ,也就是我们将余数x作为放在状态中。 #include<cstdio> #include<algorithm> #include<cstring> #includ ......

题目链接在这里：Lutece (uestc.edu.cn) 典型的状压dp，对于状压dp一般有三重循环，第一个枚举状态，第二个和第三个分别枚举一个状态到另一个状态的起点和终点。 #include "bits/stdc++.h" using namespace std; const int MAX=5 ......

目录换根DP相关资料例题 换根DP 相关资料 例题 ......

点击查看代码 #include <bits/stdc++.h> using namespace std; const int N=250,mod=998244353; int f[N][2000];//长度为i时，前pos-1项的和为j的合法数 string s; //pos位置，sum==mark ......

简单位运算模拟 class Solution { public: int findKOr(vector<int>& nums, int k) { vector<int> bit(32, 0); for(int i = 0; i < 31; i ++ ) { int cnt = 0; for(auto ......

【题解】P9753 [CSP-S 2023] 消消乐 不知道考场脑子是抽了还是有病，全程都不知道在放什么屁。 特别鸣谢：@dbxxx 给我讲解了解法一的满分做法，并让我对哈希有了更加深刻的认识；@Daidly 给我讲解了解法二。 题目链接 P9753 [CSP-S 2023] 消消乐 题意概述 给定 ......

题目链接 贪心 + Dp Part1 看上去很像背包，但是发现最后答案和堆放的顺序有关，很容易想到状压，但是复杂度不允许。 而且发现如果一个一个向上放，当前决策会有后效性，题目也不允许在开一维状态。 Part2 对于后效性，我们可以每次把箱子放在最下面，就没有后效性了。 重点是解决顺序问题，考虑两个 ......

洛谷题面 CF1810G 分析 考虑最大前缀和满足两个条件，就是所有前缀和都不超过，以及一定有一个等于。 那么就要保证它能达到最大值且一直不能高于它 设 \(dp[i][j][0/1]\) 表示前 \(i\) 个数离达到最大值还需要 \(j\) 且未/已经达到过最大值。 初始化就是 \(dp[0][ ......

题目 问有多少个长度为 \(n\) 的排列 \(P\) 满足 \(|P_i-i|=1\) 的 \(i\) 的个数恰好为 \(k\) 个 分析 设 \(dp_{i,j,k}\) 表示前 \(i\) 个数钦定 \(j\) 个数满足上述条件且现在 \(i\) 和 \(i+1\) 因此被占用的方案数。 那么 ......

ABC219 H 跟关路灯很像。 很容易注意到我们拿走的只能是一个区间，观察n的范围发现区间dp是个好想法。 朴素的想法是定义 \(f_{i,j,k,0/1}\) 为拿走i到j里面的所有数，走了k秒，现在在 i/j 的方案数。 然后发现k太大了。 咱当时的想法是希望优化复杂度，把k去掉结果发现不能保 ......

预计时间一个月,一天的量为1-2道左右,难度不均,黄-紫都有,后阶段紫 // https://www.luogu.com.cn/problem/P4141 // 对于任何一个物品对答案的贡献都是从1到n递推过去的,所以 // 只需要开一个相同的数组然后从头遍历一遍,把该物品对答案的贡献减去就可以了 ......

说明 1 简述DP1042是一款应用于 CAN 协议控制器和物理总线之间的接口芯片，可应用于卡车、公交、小汽车、工业控制等领域，支持 5Mbps CAN FD 灵活数据速率，具有在总线与 CAN 协议控制器之间进行差分信号传输的能力，完全兼容“ISO 11898”标准。2 短路保护DP1042的驱动 ......

CF809D Hitchhiking in the Baltic States-平衡树+DP Statement 给出 \(n\) 个区间 \([l_i,r_i]\) 和 \(n\) 个未知数 \(a_1,a_2,\dots,a_n\)，现在你要确定这 \(n\) 个数，使得 \(a_i\in[l_ ......

题目简述 选择的学校编号依次为 \(p1, p2, p3, ..., pk(1 ≤ p1 < p2 < ... < pk ≤ n)\)，若存 在 \(i(1 ≤ i ≤ k − 3)\) 使得 $ a_{p_i} ⊕ a_{p_{i+1}} ⊕ a_{p_{i+2}} ⊕ a_{p_{i+3}} = ......

决策单调性的概念&证明工具: 决策单调性,是在最优化dp中的可能出现的一种性质,利用它我们可以降低转移的复杂度。 首先dp中会有转移,每个状态都由若干个状态转移而来,最优化dp比较特殊,只能由一个最优的状态转移而来。 我们称之为某个状态的最优转移点。 然后,dp会有一个转移顺序,比如说按层转移,从左 ......

动态规划——决策单调性优化DP 学习笔记 决策单调性 对于最优性问题，常有状态转移方程：\(f_i = \min/\max\{f_j\dots\}\)， 形象的：如果 \(i\) 的最优转移点是 \(j\)，\(i'\) 的最优转移点是 \(j'\)，当 \(i<i'\) 时，有 \(j\le j' ......

题目背景 Farmer John has MM cows, conveniently labeled 1…M1…M, who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer ......

万物的开始，首先介绍一下动态规划（dynamic programming，DP）的基本概念：动态规划适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法耗费时间远远少于朴素解法。 动态规划总共可以分为4个步骤：1、定义子问题 2、写出子问题的递推关系 3、确定DP数组 ......