标签:动态规划

题意你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块,你需要重复下面的操作 $k$ 次:选择一个有超过一个元素的块(初始时你只有一块,即整个序列)选择两个相邻元素把这个块从中间分开,得到两个非空的块。每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。$n\le 10000...
题解 动态规划 动态规划-斜率优化DP
省选/NOI-
题意有 $N$ 块矩形土地,面积为 $W_i\times H_i$ 。可以购买单个土地,价格为面积;也可以将多个土地合并起来买,价格为 $\max W\times \max H$ 。要将所有土地买下来,求最小花费。$N\le 50000$ 。题解对于两块土地 $i,j$ ,如果 $H_i\le H_j,W_i\le W_j$ ,那么买 $j$ 的时候顺便把 $i$ 带上就行了,$i$ 就可以...
题解 动态规划 动态规划-斜率优化DP
省选/NOI-
题意有 $N$ 个商店,每个商店在 $X_i$,有 $F_i$ 个物品,价格为 $C_i$ 元。如果车上有 $P$ 个物品,每单位距离的运输费用为 $P^2$ 。从 $1\rightarrow E$,要求买 $M$ 个物品,求最小花费。$N,E\le 500 \ , \ X_i\le E$ 。题解先把 $E$ 看成一个商店,各项属性为 $X_i=E \ , \ F_i=C_i=0$ 。然后把...
题解 动态规划 动态规划-单调队列优化DP
提高+/省选-
题意有 $N$ 个点,从 $1$ 开始跳,跳到高度比当前矮的点免费,否则消耗 $1$ 。有 $M$ 次询问,每次给出最长能跳的距离,求跳到 $N$ 的最小花费。$N\le 10^6 \ , \ M\le 25$ 。题解用 $f[i]$ 表示跳到 $i$ 的最小花费,则$$f[i]=\min_{i-j\le q} \begin{cases} f[j] \ (H_j > H_i) \\ ...
题解 动态规划 动态规划-单调队列优化DP
提高+/省选-
题意有 $N$ 个数,可以进行 $K$ 次操作,每次可以选择一个区间,把其中所有数 $+1$ 。求最后最长不降子序列的长度。$N\le 10000 \ , \ K\le 500$ 。题解可以发现,每次选择区间的右端点一定是 $N$ ,否则就可能出现答案减小的情况,而不可能会增加。用 $f[i][j]$ 表示第 $i$ 个数被操作了 $j$ 次 ,前 $i$ 个数的最优情况。可以得到方程:$$...
题解 动态规划 数据结构-树状数组
省选/NOI-
题意有 $N$ 张卡片,使用过后会往前跳 $S_i$ 格。有 $M$ 个格子是厄运格,如果跳到就输了,求跳到终点的方案数。$N\le 24 \ , \ M\le 2$ 。题解用 $cnt[i]$ 表示当前走到的格子,很容易想出状压方程:$$f[i]=\begin{cases} 0 \ (cnt[i]\in M) \\ f[i]+f[i \ xor \ 2^{j-1}] \ (cnt[i]\n...
题解 动态规划 动态规划-状压DP
省选/NOI-
题意有 $N$ 个人要排队,要求一队的站在一起,共有 $M$ 队。调整队列的方法为让一部分人出队,再回到不同的空位里。求最少要让多少人出队。$N\le 100000 \ , \ M\le 20$ 。题解对每支队伍是否有序状压,用 $f[i]$ 表示状态为 $i$ 时最少的出队人数。记录第 $j$ 支队伍的人数为 $cnt[j]$ ,设之前排到了第 $l$ 个人,那么现在要排的是 $[l+1,...
题解 动态规划 动态规划-状压DP
提高+/省选-
题意有 $N$ 个人去执行 $N$ 个任务,每个人执行每个任务有不同的成功率,每个人只能执行一个任务,求所有任务都执行的总的成功率。(直接用题面)$N\le 20$ 。题解用 $f[i]$ 表示任务完成状态为 $i$ 时的最大成功率。预处理出 $1$ 的个数 $cnt[i]$ ,枚举任务 $j$ ,很容易得到方程:$$f[i]=\max f[i \ xor \ 2^{j-1} ]+s[cnt...
题解 动态规划 动态规划-状压DP
省选/NOI-
题意用 $K$ 个硬币购买 $N$ 个物品。商店不设找零,可以在购买了连续多个物品后用 一个 硬币支付。求最多能剩下多少钱。$N\le 100000 \ , \ K\le 16$ 。题解看到 $K\le 16$ ,状压。用 $f[i]$ 表示硬币使用状况为 $i$ 时能买前几个物品;预处理出 $v[i][j]$ 表示硬币 $i$ ,从 $j$ 物品开始买,能买到哪个物品;枚举当前用的硬币 $...
题解 动态规划 动态规划-状压DP
提高+/省选-
题意在一棵 $N$ 个点的树上放 $K$ 个监听器,每个监听器可以监听与它直接相连的节点,但不能监听自己。要求所有节点都被监听,求方案数。$N\le 100000 \ , \ K\le 100$ 。题解真·毒瘤题目。用 $f[x][i][0/1][0/1]$ 表示以 $x$ 节点为根的子树中除了 $x$ 都被监听了,放了 $i$ 个监听器,$x$ 上放没放监听器,$x$ 有没有被监听到 的方...
题解 动态规划 动态规划-树形DP
NOI/NOI+/CTSC
题意将一棵 $N$ 个点的树上 $K$ 个点染黑,另外的点染白。求黑点两两之间距离和加上白点两两之间距离和的最大值。$N,K\le 2000$ 。题解考虑每一条边的贡献,即为 边权 $\times ($ 一侧的黑点个数 $\times$ 另一侧的黑点个数 $+$ 一侧的白点个数 $\times$ 另一侧的白点个数 $)$ 。用 $f[x][i]$ 表示以 $x$ 为根的子树,黑点有 $i$ ...
题解 动态规划 动态规划-树形DP
省选/NOI-
题意有 $N$ 个小球,每个小球的坐标为 $(x_i,y_i)$ ,即水平为 $x_i$ ,高度为 $y_i$ , 每秒会以 $v_i$ 的速度下落。人所在的初始位置为 $x_0$ ,每秒可以移动一个单位。当人移动到小球下面的时候就可以接住这个小球并获得分数,分数为小球当前高度的 $\dfrac{1}{1000}$ 。要求接住所有小球,求最高分数。$N\le 1000$ 。题解比较容易想到区...
题解 动态规划 动态规划-区间DP
省选/NOI-
题意可以用 $x(s)$ 来表示有 $x$ 个字符 $s$ ,可以在括号内嵌套和拼接。求一个字符串的最短折叠长度。字符串长度 $N\le 100$ 。题解设需要处理的字符串为 $S$ ,用 $f[l][r]$ 表示折叠 $S_l..S_r$ 的最短长度。显然可以从两个字符串拼接而来。枚举断点 $k$ ,$f[l][r]=\min(f[l][r],f[l][k]+f[k+1][r])$ 。也可...
题解 动态规划 动态规划-区间DP
省选/NOI-
题意给一个长度为 $N$ 的木板染色,木板有初始颜色,要求染成一种颜色。每次可以选择一段连续的格子染色,颜色可以被覆盖。求至少要染多少次。$N\le 50$ 。题解用 $f[l][r]$ 表示将 $[l,r]$ 染成一种颜色的最少次数。当 $S_l=S_r$ 时,可以在染一边时顺便把另一边染了,即 $f[l][r]=\min(f[l+1][r],f[l][r-1])$ 。否则可以枚举中间点 ...
题解 动态规划 动态规划-区间DP
提高+/省选-
题意有 $N$ 座城堡和 $S$ 个玩家,每个玩家有 $M$ 个士兵。能占领城堡要求自己驻扎的兵力严格大于对方的两倍,玩家之间两两都会有独立的城堡争夺,占领第 $i$ 个城堡的收益是 $i$。现在已知 $S$ 个玩家的驻军情况,求如何分配兵力,可以获得最大收益。$S,N\le 100 \ \ \ \ M\le 20000$ 。题解很显然的背包问题,只是需要预处理一下重量。用 $v[i][j]...
题解 动态规划 动态规划-背包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 比赛-Codeforces18 比赛-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