标签:动态规划

题意给出一个 $N$ 点 $M$ 边的有向图,令 $1\rightarrow N$ 的最短路长度为 $d$ ,求 $1\rightarrow N$ 的长度不超过 $d+k$ 的路径条数。多组数据。 $N\le 100000$ ,$M\le 200000$ 。题解先跑一次反向最短路,记 $i\rightarrow n$ 的最短路长度为 $dis[i]$ 。用 $d(i,j)$ 表示 $i\ri...
题解 动态规划 动态规划-图上DP
省选/NOI-
双倍经验:洛谷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
提高+/省选-
题意在 $N\times M$ 的棋盘上放若干个炮,要求不能互相攻击,求方案个数。其中 $N,M\le 100$ 。题解将题意转化一下就是每行每列都不能放超过 $2$ 个棋子,那么可以用 $f[i][j][k]$ 表示前 $i$ 行,有 $j$ 列是有 $1$ 个棋子,有 $k$ 列是有 $2$ 个棋子的合法方案数。那么没有棋子的列数即为 $M-j-k$ 。然后分类讨论。不放继承上一步的状态...
题解 动态规划 思维题
省选/NOI-
题意定义半连通图为对于 $\forall (u,v)$ ,存在从 $u$ 到 $v$ 或从 $v$ 到 $u$ 的有向路径。给出一个有向图,求最大半连通子图中的节点个数以及最大半连通子图的个数。其中点数 $N\le 100000$ ,边数 $M\le 1000000$ 。题解显然连通图也属于半连通图,那么可以先缩点,记录每个点的新编号 $scc[]$ 以及包含节点个数 $siz[]$ ,并删...
题解 动态规划 图论-Tarjan 图论-缩点 算法-拓扑排序
省选/NOI-
首先预处理一下两个单词 $s[i],s[j]$ 是否安全并记录在 $can[i][j]$ 中,用 $f[i]$ 代表包含第 $i$ 个单词的安全组有多少个。枚举每一个小于当前单词的单词,如果他们俩安全,那么当前单词和 枚举单词所在的安全组成员 在一起也一定是安全的,所以加上答案即可。$$f[j]= \begin{cases} f[j] \\ f[j]+f[i] , can[i][j] \&a...
题解 动态规划
提高+/省选-
显然用dp,用 $f[i]$ 表示前 $i$ 辆车过桥的最短时间,枚举上一个分组的最后一辆车 $j$ 进行转移,方程式为:$$f[i]=min \begin{cases} f[i] \\ f[j-1]+len\div s[i] \times 60 & j<=i, \sum ^{i}_{k=j}w[k]<=wmax \end{cases}$$其中 $tmax$ 是这一组中最...
题解 动态规划
普及+/提高
就是一道区间dp+高精,最开始还想拿int_128来水水的,结果算算还是不太够,就老老实实写了高精。$f[st][ed][cnt]$ 表示在区间 $st..ed$ 放 $cnt$ 个乘号的最大值,转移方程式为:$$f[st][ed][cnt]=\max \{ f[st][mid][x]\times f[mid+1][ed][cnt-x-1] \}$$每次转移时枚举放乘号的位置 $(mid)$...
题解 算法-高精度 动态规划
普及+/提高
晚上做了洛谷TG试炼场的DP lv1 模块,还是大致总结一下。洛谷P1005 矩阵取数游戏区间DP。对于每行,我们可以单独处理。用 $ f[l][r] $ 表示已经取了 $ l..r $ 这个区间后的得分最大值。然后记忆化搜索即可。$ $ 肯定是爆long long了,按理来说应该要写高精的,但是我发现这玩意写高精如果没有运算符重载版的是真的恶心,然后__int128水过去了。#includ...
题解 动态规划
很久没写过总结了。紫书做了那么多道题,但是我的动规并没有找到什么感觉,也就只有普及难度的可以不看题解写,剩下的都是看着题解写完的,我还是太弱了。这里还是来总结一下吧。例题9-1 UVa1025-A Spy in the Metro$f[i][j]$表示在车站i,时刻是j,还剩多少时间(根紫书略有不同)决策有三个,上左边的车,上右边的车,如果都不开往幼儿园就等一时刻的车。注意还要判断某一时刻是...
题解 动态规划
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划40 动态规划-区间DP8 动态规划-单调队列优化DP4 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP12 动态规划-状压DP12 动态规划-线性DP9 动态规划-背包DP2 图论4 图论-LCA2 图论-Tarjan9 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束3 图论-强连通分量1 图论-最小环1 图论-最小生成树6 图论-最短/最长路15 图论-树上差分1 图论-桥1 图论-缩点4 图论-负环3 字符串2 字符串-kmp2 思维题3 数学22 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂3 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵4 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-栈1 数据结构-树状数组3 数据结构-树链剖分9 数据结构-线段树1 数据结构-队列1 比赛-Codeforces13 比赛-JX Round1 比赛-NOIp3 算法-二分/三分9 算法-位运算1 算法-倍增2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分3 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索19 算法-模拟3 算法-状态压缩3 算法-贪心4 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2