标签:动态规划-区间DP

题意在 $n(n\le 100)\times m(m\le 2)$ 的矩阵中选出 $k(k\le 10)$ 个子矩阵,使得这些子矩阵中数字和最大。子矩阵之间不能重叠。题解如果做过 CF1199F 就很容易做出来。用 $f[l][r][x][y][k]$ 表示在左下角为 $(l,x)$ ,右上角为 $(r,y)$ 的区域中选 $k$ 个子矩阵的最大和。枚举横纵的中间点,以及两部分选取的子矩阵的...
题解 动态规划 动态规划-区间DP
提高+/省选-
题意长度为 $N$ 的小写字母串,要求增加或删除字母使其变成回文串。每个字符的增加和删除有固定的花费,求花费的最小值。$N\le 2000$ 。题解区间DP,用 $[i][j]$ 表示将 $[i,j]$ 变成回文串的最小花费。如果 $S_i=S_j$ ,那么可以直接从 $f[i+1][j-1]$ 转移过来。对于上一个状态 $[i+1,j]$ ,可以删掉 $S_i$ ,也可以在右边添加一个 $...
题解 动态规划 动态规划-区间DP
提高+/省选-
双倍经验:洛谷2734 游戏 A Game (还不用滚动数组)题意有 $N$ 个数,两个人轮流取,每次可以取左右两端的数。两个人都绝顶聪明,问第一个人最多能取到多少。$N\le 5000$ 。空间限制 $64M$ 。题解用 $f[i][j]$ 表示在 $[i,j]$ 最多能取到多少,用 $sum[i][j]$ 表示 $[i,j]$ 的和。因为两个人都会取最优方案,所以方程式为:$$f[i][...
题解 动态规划 动态规划-区间DP
提高+/省选-
题意有 $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
提高+/省选-
咕咕咕。
题解 动态规划-区间DP
提高+/省选-
题意有 $N$ 个正整数,每次可以选相邻的相同的数合并,合并后得到的值为原数 $+1$ 。求合并后最大数的最大值。其中 $N\le 262144$ 。题解用 $f[i][j]$ 表示左端点为 $j$ ,能合并出 $i$ 这个数字的右端点的位置。显然 $i$ 是由 $i-1$ 转移过来的,所以我们要构造 $f[i-1][?]$ 。不妨考虑 $i+1$ ,在 $f[i][j]$ 这个右端点基础上...
题解 动态规划-区间DP 思维题
提高+/省选-
题意一个序列 $S$ ,合并两个区间 $[l,x]$ 和 $[x,r]$ 对答案的贡献为 $(S_l+S_r)\times S_x$ 。先任取 $mid$ 将序列不断二分,直到每个区间只有一个元素后再合并。求答案的最大值,以及每阶段二分时取的 $mid$ 。按照阶段从小到大,每阶段内从左到右输出。其中序列的长度 $N\le 300$ 。题解显然区间dp,就是输出二分的方法有点麻烦。我最开始是...
题解 题目-一本通 动态规划-区间DP
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划49 动态规划-区间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 比赛-Codeforces17 比赛-JX Round1 比赛-NOIp/CSP4 算法-二分/三分11 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希1 算法-多叉树转二叉树2 算法-差分3 算法-悬线法1 算法-拓扑排序1 算法-排序3 算法-搜索20 算法-模拟5 算法-状态压缩4 算法-贪心8 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2