- 2024-01-13解题报告P2501 [HAOI2006] 数字序列
P2501[HAOI2006]数字序列题目描述现在我们有一个长度为\(n\)的整数序列\(a\)。但是它太不好看了,于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。输入格式第一行是一个整数,表示序列长度\(n\)。第二行有\(n\)个整数,第\(
- 2023-09-17P2501 [HAOI2006] 数字序列
先来看第一问。发现直接做要考虑两数中间的数能否变得合法,所以按套路将\(a_i\)减去\(i\),这样就只要变成单调不降,只要两数合法中间的数就一定能变得合法。考虑不改变的那些数,它们一定单调不降,所以答案就是序列总长度减去最长不下降子序列的长度。接下来看第二问,尝试观察一些性
- 2023-09-15P2501 [HAOI2006] 数字序列
原题是思路非常值得学习的一道题第一问:首先我们感性上觉得这题应该和LIS有一点关系,但里面有一点问题:1750505018如果我们求LIS的话,我们会认为只需要改掉505050即可,但其实我们只改掉这些数,我们是无法做到让数单增的我们发现这个限制写成数学语言即为:\(a_i-a_j\geq