zhengjun dp

题目补充: 使得 a=b, 思路: 在 y<=x 好处理 在 y>x 时 利用区间dp处理 a==b 0, a!=b 1, 1要变 先预处理 把 0的 位置删了 删除多余信息 方便后面处理 然后 对于 取2个点 为 y ,另外一种操作就是 选2个连续的点直接 (他们位置差)*x 以此区间dp即可 或 ......

思路 : 找各种性质 1 每一秒只有 史莱姆进入起始点 , 然后他会选一个方向走(右或者下), 每一秒 史莱姆都会这样走 在考虑 前 t 秒内 有S个史莱姆到达这个点, 然后就会 有 s+1/2 个 往右走, s/2 往下走 而且 问t秒 只会 有 t-n-m-1 秒后的时刻影响 (诈骗t ) 于是 ......

#include<bits/stdc++.h> using namespace std; using ll=long long; const int N=1e5+10,M=2e5+10,Inf=1e9; namespace Flow{ const ll INF=1e18; const int V=N ......

"此刻发生的所有事，都是你过去选择的结果。" 最近打模拟赛在状压dp上总是没有一点思路。来重学一遍。 状态压缩：通过一串 0 1 码来清晰地表示一个集合的状态。同时，在确定了最低位的前提下，一串 0 1 码与一个二进制数一一对应。 其本质上是进行了两次操作： 给这个集合的每个状态一个编号。 通过这个 ......

目录I. Interval Addition I. Interval Addition 题意 给定一个长度为 n $(1\le n \le 23) $ 的数组 a。你可以进行一种操作：选择区间 \([l, r]\) 并给这个区间所有的数都加上一个任意的数。问你使得整个数组均为 0 所需的最小操作次数 ......

动态规划——带权二分优化DP 学习笔记 引入 带权二分其实并不一定用于优化 DP，也可能用于优化贪心等最优化的算法。 带权二分也叫 WQS 二分，最初由王钦石在他的 2012 年国家集训队论文中提出。 定义 使用情况 要解决一个最优化问题（求最大 / 最小值） 有一个限制，一般是某个参数要求一定恰好 ......

Codeforces Round 901 (Div. 2) D. Jellyfish and Mex //思路：对于大于mex的数不做处理，把0删完为结束 //dp[j]为mex更新到j所需要的最小花费 //用mex=i时更新到j，转移方程为 dp[j] = min(dp[j], dp[i] + i ......

一道经典的dp了 题目描述 给出 1,2,…,n 的两个排列 P1 和 P2​ ，求它们的最长公共子序列。 输入格式 第一行是一个数 n。 接下来两行，每行为 n 个数，为自然数 1,2,…,n 的一个排列。 输出格式 一个数，即最长公共子序列的长度。值得记录的原因是它可以转化，这个巧妙的转化我觉得 ......

动态规划——DP与最短路 学习笔记 例题：P2761 软件补丁问题，很容易写出转移方程：\(dp_s \leftarrow dp_{s \setminus F_1 \cup F_2} + t_i\)， 但是这样就出现了环，没有形成 DAG 就无法跑动态规划了，怎么办？ 可以将原问题转换为［最短路］： ......

分析 首先可以列出最基础的 DP 式子。设 \(dp_i\) 表示跳到 \(i\) 的最小花费，有： \[dp_i=\min\limits_{1\leq j < i }\{dp_j+(h_i-h_j)^2\}+C\]\[dp_1=0 \]直接算的话时间复杂度 \(O(n^2)\)。 然后化简一下式子 ......

P9408 容易想到枚举最大值，令 \(f_{i, j}\) 表示前 \(i\) 个数变为不降序列且第 \(i\) 个数为 \(j\) 的最小操作次数。 先考虑暴力转移：\(f_{i,j} = f_{i - 1, k} + \text{chg}(a_i, j)\)，其中 \(\text{chg}(i ......

CF1829G 先将整个塔变为一个直角三角形的模样。这时就可以很好的用数组表示了，这时发现答案就是一个倒着的等腰直角三角形的和（不考虑边界）。 考虑预处理。 令 \(a_i\) 为点 \(i\) 所在的行数，\(f_i\) 表示 \(i\) 号点的答案，\(g_i\) 表示 \(i\) 和 它正上方 ......

P8816 提供一种不一样的做法。 首先将每个点以横坐标为第一关键字，纵坐标为第二关键字排序。 一维的 dp 肯定不够，因为 dp 既要存最多点数，又要保存自由点的点数。 赛时没看 \(k\) 的范围，于是开了一个结构体。 \(dp_i.w\) 表示从当前起点开始且于 \(i\) 点结束的最多的点数 ......

点击查看代码 #include<bits/stdc++.h> using namespace std; int n,m; long long f[10][1024][100]; int v[1024]; void init() { for(int i=1;i<1<<n;++i) { int c=0; ......

AC自动机与dp 前言： 本篇题解隶属于https://www.cnblogs.com/linghusama/p/17742870.html部分 首先一定要理解fail跳的原理，不然很难理解第二维为什么要设置。 首先给出大致的雏形，dp_i_j表示目前拼凑出长度为i的字符串，且ac自动机上的指针在j ......

D. Round Subset 老早写过了，但是边界考虑不太清楚 https://codeforces.com/problemset/problem/837/D #include <bits/stdc++.h> #define ll long long using namespace std; co ......

题目背景：你有一个容量为 M的背包,有N个物品,每个物品的重量和价值分别为w[i]和c[i],现在选一些物品放入这个背包使装入的价值最大 1. 01背包（每件物品只有1件）：倒序枚举重量，O(N^2) E(i,n){ cin>>w>>c; for(int j=m;j>=w;--j) f[j]=max ......

完全背包是01背包的进阶版。在这里补充一下代码随想录的完全背包状态转移式的推导。有兴趣的可以先看一看原版。 状态转移方程 状态：dp[i][j] 选择前i个物品，容量为j的背包时 所选物品价值总和最大。 状态转移： dp[i][j]=max(dp[i-1][j-k* v[i]]+k* w[i]) ( ......

本场比赛难度吧不大，建议开题顺序为 \(T2-T1-T3\) 。 \(T2\) 题目描述 有 \(n\) 个高楼排成一行，每个楼有一个高度 \(h_i\)。称可以从楼 \(i\) 跳到 楼 \(j\)，当 \(i\), \(j\) ( \(i < j\) )满足以下三个条件之一： \(i+1=j\) ......

ABC298Ex 简单题。 因为有 \(\min\) 不好做，容易想到讨论 \(d(i, L)\) 和 \(d(i, R)\) 的大小。 令 \(p = \text{LCA}(L, R)\)，\(dep_L > dep_R, dist = dep_L + dep_R - 2\times dep_p\ ......

ABC273F 一道比较板的区间 \(\text{dp}\)。 先对坐标离散化，令离散化数组为 \(v\)。 令 \(f_{i,j}\) 表示能走到区间 \([v_i,v_j]\) 的最短路程，显然 \(f\) 数组初始为 \(inf\)。 但发现这样无法转移，可以再增加一维 \(k \in \{0 ......

动态规划 动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 背包 01背包 每个物体只有两种可能的状态（取与不取），对应二进制中的 \(0\) 和 \(1\)，这类问题便被称为「0-1 背包问题」。 状态转移方程： \[f_{i,j}=\max(f_{i-1,j},f_{i ......

ABC239H 简单题。 令 \(f_i\) 表示乘到 \(\ge i\) 的期望。 容易得到 \(f_i=\dfrac{\sum\limits_{j=1}^{n}f_{\lceil\frac{i}{j}\rceil}}{n}\)。 将 \(f_i\) 移到同一边，去掉系数，有 \(f_i=\dfr ......

ARC163D 发现这个竞赛图一定能被分为两个集合 \(A\)，\(B\)。满足 \(\forall u\in A,v\in B\)，均有 \(u\to v\in E\)。答案就是划分这两个集合的方案数。 证明： 首先，竞赛图缩完点后一定是一条链，对强连通分量进行标号，满足编号小的强连通分量指向编号 ......

想写但想不起来写啥🤣 orz 宝爷 orz 📕 \(\tt Beautiful\ Mirrors[5.0|B^x]\) 以下默认 \(p_i \leftarrow \dfrac{p_i}{100}\) 显然有转移方程 \[\Large f_i=p_i\times f_{i+1}+(1-p_i)\ ......

首先，我们发现，转移一颗子树的背包，实际上就是把该子树的根节点的所有儿子的子树背包合并，再与根节点合并。具体的，合并两颗子树的转移方程式如下： \[f(u,i) = \max\limits_{j+k=i}\{f(v_1,j)+f(v_2,k)\} \]于是有如下伪代码： dfs(u) : su = ......

思路 : 区间dp(区间DP的时间复杂度 不一定是 n^3 ,可能是 n^2 更具题意) 直接题 直接 区间dp, 0 Alice 赢 1 平局 2 Bob 赢 (于是 alice 尽可能小, bob 尽可能大) alice 选 l , bob 可以选 l+1, 或者 r alice 选 r , b ......

主要讲一下每一题的做法以及思考方式。 感觉难度薇 \(T1-T3-T2\) 。但是都不算难。 \(T1\) 题目描述 Jimmy 最近迷上了一款叫做方块消除的游戏。游戏规则如下：\(n\) 个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻方块颜色相同，则这两个方块属于同一区域）。为简化 ......

背包问题-完全背包 例题 题目描述 此题和原题的不同点： \(1\). 每种草药可以无限制地疯狂采摘。 \(2\). 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！ 输入格式 输入第一行有两个整数，分别代表总共能够用来采药的时间 \(t\) 和代表山洞里的草药的数目 \(m\)。 第 \ ......

背包问题-01背包 首先我们要明白什么是01背包，在下述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的 \(0\) 和 \(1\)，这类问题便被称为\(\text{「0-1 背包问题」}\)。 题目描述 有 \(N\) 件物品和一个容量为 \(M\) 的背包。第 \(i\) 件物 ......