标签 动态规划 下的文章
- 首页
- 动态规划
「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$。