标签 动态规划 下的文章

「Codeforces 1228E」Another Filling the Grid

题目链接：Codeforces 1228E

你有一个 $n \times n$ 的网格和一个整数 $k$，在每个格子中都填入一个整数，满足如下条件：

• 所有格子中的整数都介于 $1$ 到 $k$ 之间。
• 第 $i$ 行的最小值为 $1$（$1 \le i \le n$）。
• 第 $j$ 列的最小值为 $1$（$1 \le j \le n$）。

请求出填数的方案数，答案对 $10 ^ {9} + 7$ 取模。

数据范围：$1 \le n \le 250$，$1 \le k \le 10 ^ {9}$。

「Codeforces 1204E」Natasha, Sasha and the Prefix Sums

题目链接：Codeforces 1204

Natasha 最喜欢的数字是 $n$ 和 $1$，Sasha 最喜欢的数字是 $m$ 和 $-1$。某一天他们写下了长度为 $n + m$ 且包含恰好 $n$ 个 $1$ 和 $m$ 个 $-1$ 的所有可能的序列。对于每一个序列计算出它的最大前缀和（允许为空）；形式化地，我们定义 $f(a)$ 表示序列 $a_{1, \dots, l}(l \le 0)$ 的最大前缀和，那么有：

$$ f(a) = \max \left (0, \max _ {i = 1} ^ {l} \sum _ {j = 1} ^ {i} a_{j} \right ) $$

现在他们想要对于所有满足条件的序列，求出 $f(a)$ 的总和。答案对 $998244853$ 取模。

数据范围：$0 \le n, m \le 2000$。

「Codeforces 1189F」Array Beauty

题目链接：Codeforces 1189F

我们定义一个序列 $b_{1}, b_{2}, \dots, b_{n} (n > 1)$ 的「美丽值」为 $\min_{1 \le i < j \le n} \lvert b_{i} - b_{j} \rvert$。

我们给定一个序列 $a_{1}, a_{2}, \dots, a_{n}$ 个一个数字 $k$。请计算出所有长度恰好为 $k$ 的子序列的「美丽值」之和，答案对 $998244353$ 取模。

数据范围：$2 \le k \le n \le 1000$，$0 \le a_{i} \le 10 ^ {5}$。

「Codeforces 1199F」Rectangle Painting 1

题目链接：Codeforces 1199F

有一个大小为 $n \times n$ 的网格图。其中一些格子是黑色的，其余格子都是白色的。你每次操作可以任意选择一个大小为 $h \times w$ 的矩形并把它全部染成白色，花费为 $\max(h, w)$。现在你想把所有格子都染成白色，请求出最小花费。

数据范围：$1 \le n \le 50$。

「2019 Multi-University Training Contest 2」Everything Is Generated In Equal Probability

题目链接：HDU 6595

Y_UME 有一个整数 $N$ 和一串有趣的代码：

首先，他先等概率随机一个正整数 $n \in [1, N]$，再等概率随机一个长度为 $n$ 的排列。最后他会将这个排列传入函数 $\text{Calculate}$ 并得到一个返回值。请你求出这个值的期望，答案对 $998244353$ 取模。

本题有多组数据。

数据范围：$1 \le N \le 3000$，$\sum N \le 5 \times 10 ^ {4}$。

「2019 Multi-University Training Contest 1」Typewriter

题目链接：HDU 6583

有一天，Jerry 发现了一个奇怪的打字机。这个打字机又 $2$ 种模式：第一种模式可以花费 $p$ 的代价在最后插入一个任意字符；第二种模式可以花费 $q$ 的代价复制任意一个子串并插在最后。

现在 Jerry 想要给 Tom 写一封信，这封信可以用一个只包含小写字母的字符串 $S$ 表示。可惜 Jerry 很穷所以他想知道写这封信的最小花费。

本题由多组数据。

数据范围：$1 \le \lvert S \rvert \le 2 \times 10 ^ {5}$，$\sum \lvert S \rvert \le 5 \times 10 ^ {6}$。

「2019 Multi-University Training Contest 1」Blank

题目链接：HDU 6578

有 $n$ 个格子排成一行，从左往右标号为 $1$ 到 $n$。

Tom 想要将每个格子填上 $\{0, 1, 2, 3\}$ 中的一个数字。但是他有 $m$ 条限制：第 $i$ 条限制为区间 $[l_i, r_i]$ 中必须有恰好 $x_i$ 种不同的数字。

请你求出满足所有限制的填数字的方案数量，答案对 $998244353$ 取模。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 15$，$1 \le n \le 100$，$0 \le m \le 100$，$1 \le l_i \le r_i \le n$，$1 \le x_i \le 4$。

「Codeforces 1178F2」Long Colorful Strip

题目链接：Codeforces 1178F2

世界上有 $n +1$ 种不同的颜色，从 $0$ 到 $n$ 标号。现在你有一张长度为 $m$ 的纸，所有位置的初始颜色均为 $0$。

Alice 通过如下步骤队这张纸染色。她按顺序使用颜色 $1$ 到 $n$ 染色，对于第 $i$ 种颜色，她选择两个整数 $1 \le a_i \le b_i \le m$ 满足位置 $[a_i, b_i]$ 的颜色相同，然后把区间 $[a_i, b_i]$ 都染成颜色 $i$。

通过所有操作，Alice 需要把第 $i$ 个位置染成颜色 $c_i$，你需要求出满足条件的序列对 $\{a_i\}_{i = 1} ^ {n}, \{b_i\}_{i = 1} ^ {n}$ 的数量，答案对 $998244353$ 取模。

数据范围：$1 \le n \le 500$，$n \le m \le 10 ^ 6$，$1 \le c_i \le n$，$\forall 1 \le j \le n, \exists k, c_k = j$。

「Luogu 4389」付公主的背包

题目链接：Luogu 4389

付公主有一个可爱的背包，这个背包最多可以装 $10 ^ 5$ 大小的东西。付公主有 $n$ 种商品，她要准备出摊了。每种商品体积为 $V_i$，都有 $10 ^ 5$ 件。

给定 $m$，对于整数 $s \in [1, m]$，请你回答用这些商品恰好装 $s$ 体积的方案数。

数据范围：$1 \le n \le 10 ^ 5$，$1 \le V_i \le m \le 10 ^ 5$。

「BZOJ 2173」整数的 lqp 拆分

题目链接：BZOJ 2173

lqp 在为出题而烦恼，他完全没有头绪，好烦啊……

他首先想到了整数拆分。整数拆分是个很有趣的问题。给你一个正整数 $n$，对于 $n$ 的一个整数拆分就是满足任意 $m > 0$，$a_1, a_2, a_3, \dots, a_m > 0$，且 $a_1 + a_2 + a_3 + \dots + a_m = n$ 的一个有序集合。通过长时间的研究我们发现了计算对于 $n$ 的整数拆分的总数有一个很简单的递推式，但是因为这个递推式实在太简单了，如果出这样的题目，大家会对比赛毫无兴趣的。

然后 lqp 又想到了斐波那契数。定义：

$$ f_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ f_{i - 1} + f_{i - 2} & n > 1 \end{cases} $$

$f_n$ 就是斐波那契数的第 $n$ 项。但是求出第n项斐波那契数似乎也不怎么困难……lqp 为了增加选手们比赛的欲望，于是绞尽脑汁，想出了一个有趣的整数拆分，我们暂且叫它：整数的 lqp 拆分。

和一般的整数拆分一样，整数的 lqp 拆分是满足任意 $m > 0$，$a_1, a_2, a_3, \dots, a_m > 0$，且 $a_1 + a_2 + a_3 + \dots + a_m = n$​ 的一个有序集合。但是整数的 lqp 拆分要求的不是拆分总数，相对更加困难一些。

对于每个拆分，lqp 定义这个拆分的权值 $\prod_{i = 1} ^ m f_{a_i}$，他想知道对于所有的拆分，他们的权值之和是多少？

由于这个数会十分大，lqp 稍稍简化了一下题目，只要输出对于 $n$ 的整数 lqp 拆分的权值和模 $10 ^ 9 + 7$ 即可。

数据范围：$1 \le n \le 10 ^ 6$。