动态规划
https://codeforces.com/contest/1107/problem/E 题目大意 给出一个 $n$ 长的 $01$ 串 $S$ 和数组 $a$。每次操作可以从中删除一个连续的，相同字符的段，并把剩余的段按顺序连起来。每次删掉 $len$ 长的段的收益为 $a_{len}$，问最大收益是多少。 $1 \le n \le 100$。$1
…
https://codeforces.com/contest/571/problem/B 题目大意 给出 $n$ 长的数组 $a$，及某数 $k$，可以任意调整 $a$ 中元素位置，需要最小化 $$ \sum_{i = 1}^{n - k} |a[i] - a[i + k]| $$ 。 问这个最小值是多少。 $2 \le n \le 3 \times 10^5$。$1 \le \min(5000, n - 1)$。$-10^9 \le a[i] \le 10^9$
…
https://codeforces.com/contest/1156/problem/D 题目大意 给出一棵 $n$ 个点的树，边上有 $0$ 或 $1$ 的权值。问有多少个 $u$ 到 $v$ 的简单路径（$u \neq v$）满足该路径通过任何边权为 $1$ 的边后不再经过边权为 $0$ 的边。 $2 \le n \le 2 \times 10^5$。 简要题解 如果我们固定了某个根，让
…
https://codeforces.com/contest/903/problem/F 题目大意 给出 $4 \times n$ 的矩阵 $f$，其中有 ‘.’ 和 ‘*'。可以用 $a_i$ 点花费将 $i \times i$ 的某个子矩阵中的 ‘*’ 全部变为 ‘.'，问将整个矩阵都变为 ‘.’ 的最小花费。 $4 \le n \le 1000$。 $1 \le a_i \le 1000$ 固定给
…
https://codeforces.com/contest/1487/problem/E 题目大意 给出 $4$ 个数组分别长 $n_i$。要求各从中选取一个元素，使得选出的和最小，问这个最小和是多少。有一些第 $1, 2$ 数组之间，$2, 3$ 数组 $3, 4$ 数组之间的下标的组是互斥的，各有 $m_i$ 个，互斥的下标不能同时选。
…
https://codeforces.com/contest/985/problem/E 题目大意 给出 $n \ (\le 5 \times 10^5)$ 根铅笔，要求放入 $k \ (1 \le k \le n)$ 个盒子。每只铅笔有一个属性 $a_i \ (1 \le a_i \le 10^9)$。 要求盒子要么为空，要么有至少 $k$ 只铅笔，且在同一盒子中的任意一对 $a_i, a_j$ 满足 $|a_i - a_j| \le d$ 其中 $0 \le d \le
…
https://codeforces.com/contest/2061/problem/C 题目大意 给出 $n \ (1 \le n \le 2 \times 10^5)$ 个人。每个人可以说谎或诚实。诚实的人总说真话，说谎的人可以说真话或者假话。任意两个说谎的人不相邻。每个人 $i$ 做出了如下论断：$i$ 左侧有 $a_i \ (0 \le a_i \le n)$ 个人说谎。问最多有多
…
https://codeforces.com/contest/1922/problem/F 题目大意 给出 $n$ 长的数组和颜色数 $x$，满足 $(1 \le x \le n \le 100)$。数组的值 $a_i \ (1 \le a_i \le x)$ 代表每个位置的颜色。你可以执行以下操作若干次： 选取 $1 \le l \le r \le n$ 和 $1 \le k \le x$，满足 $\forall \ l \le i \le r, a[i] \neq k$。将
…
https://codeforces.com/contest/808/problem/E 题目大意 给出 $n \ (n \le 10^5)$ 个物品和总容积为 $m \ (m \le 3 \times 10^5)$ 的背包。n 个物品的体积和价值分别为 $w_i \ (1 \le w_i \le 3)$ 和 $c_i \ (1 \le c_i \le 10^9)$。 问可以装入背包的（不超过 $m$ 的）最大价值。 简要题解 显然这是一个 $01$ 背包问题
…
https://codeforces.com/contest/1202/problem/C 题目大意 给出一个 $WSAD$ 操作序列 $S \ (|S| \le 2 \times 10^5)$，其中 $W$ 为 $x = x - 1$ $A$ 为 $y = y - 1$ $S$ 为 $x = x + 1$ $D$ 为 $y = y + 1$ 可以在任意位置加入最多一个字符，使得机器人运行这个序列而不移出边界所需的矩形框面积最小
…
https://codeforces.com/contest/628/problem/D 题目大意 给出 $m \ (1 \le m \le 2000)$ 和数字 $d \ (0 \le d \le 9)$，给出两个字符串表示的没有前导零的大整数 $a, b \ (1 \le a \le b \le 10^2000)$。 问在区间 $[a, b]$ 中有多少数字 $x$ 符合能被 $m$ 整除，且从高向低数的偶数位（$1-
…
https://codeforces.com/contest/797/problem/E 题目大意 给出 $n \ (\le 10^5)$ 长的数组 $a \ (1 \le a_i \le n)$。 给出 $q$ 个询问。每个询问给出 $p \ (1 \le p \le n)$ 和 $k \ (1 \le k \le n)$。问要对 $p$ 执行多少次 $p = p + a[p] + k$ 才能使 $p > n$。 简要题解 对于固定的 $k$ 这是一道动态规划题目
…
https://codeforces.com/contest/792/problem/C 题目大意 用字符串给出一个十进制大整数 $S \ (|S| \le 10^5)$。问最少删掉多少位可以得到一个没有前导零的能被 $3$ 整除的数。输出这个数。 简要题解 允许前导零的话这题非常水，直接 $dp[i][j]$ 表示到第 $i$ 位 $\mod 3$ 为 $j$ 的最多选数数
…
https://codeforces.com/contest/940/problem/E 题目大意 给出 $n \le 10 ^ 5$ 长的数组 $a (1 \le a_i \le 10 ^ 9)$ 和常数 $c \le 10^5$ ，可以将数组分为一些连续的子数组。对于每个子数组，可以将其最小的 $\lfloor \frac{len}{c} \rfloor$ 个元素的权值减去。问剩余权值的和的最小值是多少。 简要题解 重要观察：最终
…
https://codeforces.com/contest/713/problem/C 题目大意 给定 $n \le 3000$ 的数组 $a$。每次操作可以使数组中的某个位置的值 $+1$ 或 $-1$。 问最少得操作次数使得数组严格单调递增。 简要题解 重要的 trick： $a_i < a_{i + 1} \iff a_i + 1 \le a_{i + 1} \iff a_i + 1 - i \le a_{i + 1} - i \iff a_i
…
题目链接 题目大意 给定 $n \le 500$ 个值的集合（值分别为 $a_i \le 500$）和一个值 $k \le 500$。 保证某个子集的和为 $k$。问对于子集和为 $k$ 的所有子集，有多少种不同的子集和，并输出这些可能得子集和。 简要题解 最初的想法
…