题意在 $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$ 个子矩阵的最大和。枚举横纵的中间点，以及两部分选取的子矩阵的...
题意长度为 $N$ 的小写字母串，要求增加或删除字母使其变成回文串。每个字符的增加和删除有固定的花费，求花费的最小值。$N\le 2000$ 。题解区间DP，用 $[i][j]$ 表示将 $[i,j]$ 变成回文串的最小花费。如果 $S_i=S_j$ ，那么可以直接从 $f[i+1][j-1]$ 转移过来。对于上一个状态 $[i+1,j]$ ，可以删掉 $S_i$ ，也可以在右边添加一个 $...
双倍经验：洛谷2734 游戏 A Game （还不用滚动数组）题意有 $N$ 个数，两个人轮流取，每次可以取左右两端的数。两个人都绝顶聪明，问第一个人最多能取到多少。$N\le 5000$ 。空间限制 $64M$ 。题解用 $f[i][j]$ 表示在 $[i,j]$ 最多能取到多少，用 $sum[i][j]$ 表示 $[i,j]$ 的和。因为两个人都会取最优方案，所以方程式为：$$f[i][...
题意有 $N$ 个小球，每个小球的坐标为 $(x_i,y_i)$ ，即水平为 $x_i$ ，高度为 $y_i$ ， 每秒会以 $v_i$ 的速度下落。人所在的初始位置为 $x_0$ ，每秒可以移动一个单位。当人移动到小球下面的时候就可以接住这个小球并获得分数，分数为小球当前高度的 $\dfrac{1}{1000}$ 。要求接住所有小球，求最高分数。$N\le 1000$ 。题解比较容易想到区...
题意可以用 $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])$ 。也可...
题意给一个长度为 $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])$ 。否则可以枚举中间点 ...
双倍经验：洛谷3146题意有 $N$ 个正整数，每次可以选相邻的相同的数合并，合并后得到的值为原数 $+1$ 。求合并后最大数的最大值。其中 $N\le 262144$ 。题解用 $f[i][j]$ 表示左端点为 $j$ ，能合并出 $i$ 这个数字的右端点的位置。显然 $i$ 是由 $i-1$ 转移过来的，所以我们要构造 $f[i-1][?]$ 。不妨考虑 $i+1$ ，在 $f[i][j...
题意一个序列 $S$ ，合并两个区间 $[l,x]$ 和 $[x,r]$ 对答案的贡献为 $(S_l+S_r)\times S_x$ 。先任取 $mid$ 将序列不断二分，直到每个区间只有一个元素后再合并。求答案的最大值，以及每阶段二分时取的 $mid$ 。按照阶段从小到大，每阶段内从左到右输出。其中序列的长度 $N\le 300$ 。题解显然区间dp，就是输出二分的方法有点麻烦。我最开始是...