标签:动态规划-线性DP

题意有一个只有 $-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
提高+/省选-
题意从一个数列中选出一些数,要求不能有超过 $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}^i \{f[j-1] - sum...
题解 动态规划 动态规划-线性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
提高+/省选-