标签:动态规划

题意给出一个数字串,要求用逗号将其分成若干个严格递增的数。如果有多解要求最后一个数最小,如果还有多解要求字典序最大。数字串长度 $\le 500$ 。题解先正着推出最后一个最小的数。用 $f[i]$ 代表以 $i$ 结尾的数的最近的开头,可以逆序枚举 $j$ ,如果 $[f[j-1],j-1] < [j,i]$ ,那么 $f[i]=j$ 。然后反着推一个最大的数。用 $g[i]$ 表示...
题解 动态规划 动态规划-线性DP
省选/NOI-
题意有形成环形的 $N$ 个机器人工厂,购买机器人的价格为 $V_i$ 。连接 $i\rightarrow i+1$ 的道路编号为 $i$ ,在时间 $j$ 的金币数为 $s[i][j]$ 。每次可以在任意工厂购买一个机器人,机器人最多可以走 $P$ 条边,并收集边上的金币。不能同时存在多个机器人。求 $M$ 的时间内最多能收集多少金币。$N,M\le 1000$ 。题解用 $f[i]$ 表...
题解 动态规划
提高+/省选-
题意你正在玩一个关于长度为 $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-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划52 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP16 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP3 图论4 图论-LCA4 图论-Tarjan11 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束4 图论-强连通分量2 图论-最小环1 图论-最小生成树6 图论-最短/最长路19 图论-树上差分2 图论-树的直径4 图论-桥1 图论-缩点5 图论-负环4 字符串3 字符串-kmp2 思维题3 数学26 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-并查集2 数据结构-栈1 数据结构-树状数组6 数据结构-树链剖分10 数据结构-线段树5 数据结构-队列1 比赛-Codeforces21 比赛-JX Round1 比赛-NOIp/CSP5 算法-KM算法1 算法-二分/三分12 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希2 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序2 算法-排序3 算法-搜索21 算法-模拟5 算法-状态压缩4 算法-贪心10 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2