Loading... ## 动态规划 --- ### 背包问题 #### 01背包 - 正常01背包 - 必须装满？ - 初始化$f[i] = 0, f[other] = -\infty$ #### 多重背包 - 二进制拆分 --- ### 热身题 #### 数字三角形+ - 给出一个数字三角形，从第一行走到最后一行，每次只能往正下或者正右下走。每次累积经过的数，要求和最大。 - 第X行第Y列这个点必须经过。 - $O(n^2)$ - 题解：先从第一层到第x层跑一遍数字三角形，然后把第x行除第y列所有数赋为负无穷，然后再在下边跑一次数字三角形即可。 --- #### 花店橱窗问题 - 给定一个n*m的矩阵A(n<=m)，求一个序列a1,a2,…,an满足$1<=a_1<a_2<…<a_n\leq m$。使得$A[1][a_1]+A[2][a_2]+…+A[n][a_n]$最大。 - A可能有负数。 - $O(nm^2)$ - 题解：$f[i,j]$表示第i行最后选到了第j列的最大值。 - $f[i,j]=max\{f[i-1,k]\}+a[i,j](1\leq k<j)$ --- #### 烽火问题 - 给定n个非负整数，选择其中若干数字，使得每连续k个数中至少有一个数被选出。 - 要求选择的数字之和尽可能小。 - $O(n^2)$ - $f[i]$表示上一个数选择的是第i个数。 - $f[i]=max(f[j])+a[i]$ --- ### 0/1背包进阶 #### 0/1背包+ - 有n个任务，在一台机器上完成，机器一次只能做一个任务，第i个任务需要ti个连续的时刻完成，截止日期在第di个时刻。在截止日期前完成能得到收益vi。 - 安排顺序，使得收益最大。 - $n<=1000，max{di}<=10000$ --- #### 0/1背包++ - 有n个物品，体积为m的背包，每个物品有一个价值vi，和体积ti，选择若干物品，使得体积之和不超过m的情况下价值之和最大。 - 对于任意第i个物品，求第i个物品一定不在背包时的最大价值。 - $n<=1000，m<=10000$ - $f[i][j]$表示i从1到n取。 - $g[i][j]$表示i从n到1取。 - 然后对于不取第p个，即为$f[p-1][j]+f[p+1][v-j]$ --- ### DP基础优化 - 减少状态数 - 减少状态转移时间 #### problem 1 - 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。 - 题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。 - $1<=s<=t<=10，L<=10^9$，石头个数<=100 - $f[x] = min( f[x-j] + stone[x] ), (s\leq j\leq t)$ - 但是，x高达10^9，难以计算 - 但也容易发现，最多100个石子，所以很多时候两个石子距离隔得很远，这时后一石子坐标前的若干个连续的点都可达。 - 稍微证明一下： - 当 s != t 时，存在 p 使得 s <= p < p+1 <= t - 显然有 gcd(p, p+1) = 1 - 当Q >= p*(p-1)时，p*x + (p+1)*y = Q 一定有非负整数解 - 也即，当Q足够大时，可以仅通过走若干个p步和p+1步，从而走长度恰好为Q的距离 --- #### [传纸条](https://www.luogu.org/problemnew/show/P1006) - 你有一个n*m的矩阵，第i行第j列有ai,j个金币，有两个人都从(1,1)出发向右或者向下走到(n,m)，并拿到经过的金币，要求获得金币个数最多。 - $n,m\leq 200$ ### 前缀和优化DP #### [花店橱窗问题](https://www.luogu.org/problemnew/show/P1854) - 给定一个n*m的矩阵A(n<=m)，求一个序列$a_1,a_2,…,a_n$满足$1\leq a1<a2<…<an\leq m$。使得$A[1][a_1]+A[2][a_2]+…+A[n][a_n]$最大。 - A可能有负数。 - $O(nm)$ - 预处理$s(i,j)$为第i行前j个的最大值，每行转移时求最大值直接$O(1)$更新。 --- #### poj3046 - T种数，第i种数有a[i]个，总共有A个数。问取其中X个数作为子集，有多少种不同的子集。计算L<=X<=H的子集数之和，结果mod 1000000 - $1\leq T\leq 1000, 1\leq a[i]\leq 100$，即$1 \leq A \leq 100000, L\leq H\leq A$ - 基本想法：可以类比为把求max改为求sum的多重背包，所以基本的递推关系很好写，dp(i,j) = sum dp(i-1)(j-k) 其中k = 0~a[i] ，dp(i,j)表示前i种数，其中j个数作为子集的取法。 - 很明显，这样做会超时、超空间，超空间好说，是基本的滚动数组。我们主要解决超时的问题。 --- ### 单调性优化 #### 最长上升子序列问题 - 有n个数，找到一个子序列，使得这些数单调递增，且这个子序列长度最大。 - $O(nlogn)$ - 普通方法，$f[i]=max\{f[j]\}+1(a_j<a_i且j<i)$ - 优化，对于最长上升子序列长度为i的，一定有结尾最低高度$h_i$并且这个高度一定是单调递增的，所以： 1. 枚举i从1道n 2. 对于当前$a_i$在$h_i$上做一个二分。 3. 更新f数组 4. 通过f的更新来更新长度为$f[i]$的末尾最低高度 --- #### 经典问题 - 给定一个队列，维护三个操作。 1. 将一个数x压入队列中。 2. 求队列中数的最大值。 3. 弹出队列尾的数。 - $Q<=1000$。 - $Q<=100000$。 --- #### 烽火传递 - 给定n个非负整数，选择其中若干数字，使得每连续k个数中至少有一个数被选出。 - 要求选择的数字之和尽可能小。 - $O(n)$ - 令$f[i]$表示只考虑前i个数，并且第i个数也选择了，并且此时$1$到$i$是满足条件的这个最小总和是多少。 - 有$f[i]=min{f[j]}+a[i]$，其中j-i不超过k。 - 时间复杂度$O(nk)$。 - 考虑优化 --- #### 最大字段和 - 有n个数，连成一个环，求最大子段和。（即对于所有区间的和求最大值） - 数字可以为负。 - $n<=1000000$。 --- #### k背包问题(多重背包) - 一个容量为m的背包，有n个物品，第i个物品的体积为wi，价值为ci，有ki个。 - 选择若干物品，使得体积总和不超过m的情况下价值总和最大。 - 能否利用单调队列进行优化？ - $O(nm)$ --- ### 树形DP #### 没有上司的舞会 - 给定一棵有点权的树，选择若干点，使得选出的点任意两个点都不相连，且选出的点权和最大。 - $n\leq 100000$。 --- #### 没有上司的舞会+ - 给定一个树套环，选择若干点，使得选出的点任意两个点都不相连，且选出的点权和最大。（基环树） - $n<=100000$。 #### 分析 - 有环怎么办？ - 基环树一般先把树上的情况处理。 - 先找到环，把每个环上的点为根，进行计算。 - 这样可以把基环树变成环，进行破环成链。 - $f(i,0/1,0/1)$记录前i个，第i个是否被选，和第一个是否被选。 - $f(i,1,0/1)=f(i-1,0,0/1)+a(i,1)$ - $f(i,0,0/1)=max(f(i-1,0,0/1),f(i-1,1,0/1))+a(i,0)$ - 那么答案就是$f(k,1,0)$或者$f(k,0,0/1)$ --- #### 最远距离 - 给定一棵带边权的树，求最远的两个点距离是多少。 #### 分析 - 对于每一个点，求其子树上的最长链a和次长链b，然后求$a_i+b_i$的最大值。 --- #### 快餐店 - 给定一棵带边权有n个点的树，要求以每个点出发，最远能走到哪里，距离是多少。 - $n\leq 100000$。 #### 分析 - 计算每个点能向下走的最远距离$f(x)$ - 对于每一个节点，维护$g(x)$表示这个点向上走的最长距离。所以$g(x)=max(g(fa),f(bro)+len(bro,fa))+len(x,fa)$ --- ### 状态压缩DP - 状态压缩，一般用一个表示状态的数字来表征一堆元素的状态，如用2^10以内的二进制数表示10个元素的有无（0/1） - 最大特征：某一个重要数据的规模特别小 - 常见优化：预处理哪些状态是合法的，以及状态转移的可行性，减少状态数和状态转移数。 #### 互不侵犯+ - 在N×N的棋盘里面放若干国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。 - N<=15。 Last modification：January 27, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏