Description

在 $T\times T$ 的正方形网格上（左下角格点坐标为 $(0,0)$，右上角为 $(T,T)$，共 $(T+1)^2$ 个格点），给定 $n$ 个关键点，保证横纵坐标都互不相同。要求选出尽可能多的关键点，使其按横坐标从小到大排序后，纵坐标也单调增。在此基础上，最小化以相邻两点为对角线的长方形面积总和。

$1\le n\le 2\times 10^5,1\le T\le 10^6$

Read More

$+1$ 操作的贡献不好计算，但是由于操作数很少，我们完全可以记录下最低 $\log k$ 位的状态，这样总状态数是 $O(k^3)$ 的，转移 $O(1)$，故总复杂度 $O(k^3)$。

Read More

CF1784D Wooden Spoon

这类问题通常可以按两种顺序 dp，本题中我们需要限制每组中最小的数依次递减，一种显然的想法是从大到小 dp，对于每个数考虑该数是与之前的某些数构成一组还是不做任何操作，类似于 ARC093F，当然由于我们需要对第一个数的每种取值计算方案数，所以 dp 需要反向，转移过程中的组合系数可能会很反常。另一种是从后向前，从小到大 dp，在填数的过程中留下一些空位，在后期对每个数决策是去填上之前的空位还是新开一组。两种方法都是 $O(n2^n)$ 的。

Read More

CF808G Anthem of Berland

数据范围明示 dp。首先在模式串上跑 kmp，预处理失配指针，dp 时遇到问号就暴力枚举字符集中每个字母，复杂度为 $O(|\Sigma|\cdot|S|\cdot|T|)$，可以卡过。

Read More

Description

给定序列 $a_1,a_2,\dots,a_n$。

每次操作可以从 $i$ 跳到 $j$，费用为 $\min\{a_i,a_{i+1},\dots,a_j\}\times (j-i)^2$。

对于每个 $k,1\le k\le n$，求出从 $1$ 到达 $k$ 的最小费用。

Read More