标签:动态规划

双倍经验:洛谷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,还剩多少时间(根紫书略有不同)决策有三个,上左边的车,上右边的车,如果都不开往幼儿园就等一时刻的车。注意还要判断某一时刻是...
题解 动态规划