标签:动态规划-线性DP

题意有一个 $m(m\le 20)$ 个点 $e$ 条边的无向图,有 $n(n\le 100)$ 个时刻需要从 $1\rightarrow m$ (保证可以到达)。每个点都有些时刻无法通行,如果更换道路还需要额外交 $k$ 元。求最小花费。题解用 $f[i]$ 表示前 $i$ 个时刻的最小花费,$x$ 表示最短路径。枚举与 $i$ 路径相同的区间起点 $j$ ,可以得到方程:$$f[i]=\...
题解 图论-最短/最长路 动态规划-线性DP
提高+/省选-
题意给出一个数字串,要求用逗号将其分成若干个严格递增的数。如果有多解要求最后一个数最小,如果还有多解要求字典序最大。数字串长度 $\le 500$ 。题解先正着推出最后一个最小的数。用 $f[i]$ 代表以 $i$ 结尾的数的最近的开头,可以逆序枚举 $j$ ,如果 $[f[j-1],j-1] < [j,i]$ ,那么 $f[i]=j$ 。然后反着推一个最大的数。用 $g[i]$ 表示...
题解 动态规划 动态规划-线性DP
省选/NOI-
题意有一个只有 $-1,0,1$ 的序列,每次操作可以使 s[i]+=s[i-1] ,求最少要操作几次使得序列单调不降。无解输出 BARK序列长度 $N\le 1000000$ 。题解用 $f[i][j]$ 表示前 $i$ 个数,$s[i]=j-1$ 时的最少操作次数。然后对于每一位的值分类讨论即可。代码里很显然了,我懒得再写一遍了。#include<bits/stdc++.h>...
题解 动态规划 动态规划-线性DP
省选/NOI-
题意有一个序列,要求修改尽可能少的数,使得这个序列变成单调上升序列。输出最少需要修改多少个数,以及在修改最少的前提下,每个数改变的绝对值之和的最小值。序列长度 $N\le 35000$ 。题解子问题1如果只是单调不降就很简单,但这题要求单调上升。假设可以保留 $S_i,S_j \ (i < j)$ ,则需要满足 $S_j - S_i \geq j-i$ ,即 $S_j - j\geq ...
题解 动态规划 动态规划-线性DP
省选/NOI-
题意有 $A,B$ 两个字符串,要从 $A$ 中选出 $k$ 个子串,按原顺序排列后形成 $B$ 。求方案数。$A,B$ 的长度为 $N,M$ ,$N\le 1000 \ , \ M\le 200$ 。题解用 $f[i][j][k]$ 表示取到 $A_i,B_j$ ,选了 $k$ 个子串的方案数。可以枚举当前子串的长度 $l$ ,这样要求 $A_{[i-l+1,i]}$ 和 $B_{[j-l...
题解 动态规划 动态规划-线性DP
提高+/省选-
双倍经验:洛谷1868 饥饿的奶牛题意从 $N$ 个区间中选取一些不重叠的区间,使得总长度最大。$N\le 10000 \ \ L,R\le 30000$ 。题解用 $f[i]$ 表示前 $i$ 个数选取区间的最大总长度,答案即为 $f[n]$ 。如果存在一个区间 $[y,x]$ ,那么 $f[x]$ 就可以从 $f[y]$ 转移过来。方程式为:$$f[x] = \max \begin{ca...
题解 动态规划 动态规划-线性DP
提高+/省选-
题意有 $N$ 个格子,每个格子有权值。最开始每次只能跳 $d$ 格,可以通过改进跳 $d-g..d+g$ 格。求满足能获得最少 $k$ 权值的最小的 $g$ 。$N\le 500000$ 。题解可以对 $g$ 二分答案,然后进行验证。令 $f[i]$ 为前 $i$ 个格子可以获得的最大权值,转移方程式为:$$f[i] = \max_{j=1}^{i-1} f[j]+s[i] \ (d-g\...
题解 动态规划 算法-二分/三分 动态规划-线性DP
提高+/省选-
双倍经验:洛谷2034 选择数字题意从一个数列中选出一些数,要求不能有超过 $k$ 个连续的数,求这些数的最大和。数列长度 $N\le 100000$ 。题解令 $f[i]$ 表示前 $i$ 个数的最优解,$sum[i]$ 表示前缀和,转移方程式为:$$f[i] = \max_{j=i-k}^i f[j-1] + sum[i] - sum[j]$$$$f[i] = \max_{j=i-k}^...
题解 动态规划 动态规划-线性DP 动态规划-单调队列优化DP
提高+/省选-
双倍经验:洛谷2687 逢低吸纳,全部改成 double 就可以水过。题意求最长下降子序列的长度和个数。如果两个序列的值相同,则认为这两个序列相同,只算一个。序列长度 $N\le 5000$ 。题解长度很好求,用 $f[i]$ 表示以 $i$ 结尾的最长下降子序列的长度:$$f[i] = \max_{j=1}^{i-1} f[j]+1 \ (s[j] > s[i]) \tag{1}$...
题解 动态规划 动态规划-线性DP
提高+/省选-
题意用两个栈进行排序,只有入栈和出栈操作,求字典序最小的操作序列。如果无法排序输出 No 。数列长度 $N\le 1000$ 。题解先考虑单栈排序。如果存在 $i < j < k$ 但 $S_k < S_i < S_j$ 就无法进行排序。这道题有两个栈,可以对所有矛盾关系 $(i,j)$ 建边,然后跑一遍 $\text{dfs}$ 进行染色,判断是否有矛盾。枚举所有的...
题解 动态规划 数据结构-栈 动态规划-线性DP
提高+/省选-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划50 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP14 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP2 图论4 图论-LCA3 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路17 图论-树上差分2 图论-桥1 图论-缩点4 图论-负环3 字符串3 字符串-kmp2 思维题3 数学25 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分10 数据结构-线段树3 数据结构-队列1 比赛-Codeforces19 比赛-JX Round1 比赛-NOIp/CSP4 算法-KM算法1 算法-二分/三分11 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索20 算法-模拟5 算法-状态压缩4 算法-贪心8 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2