P2501[HAOI2006]数字序列题目描述现在我们有一个长度为\(n\)的整数序列\(a\)。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。输入格式第一行是一个整数，表示序列长度\(n\)。第二行有\(n\)个整数，第\(

先来看第一问。发现直接做要考虑两数中间的数能否变得合法，所以按套路将\(a_i\)减去\(i\)，这样就只要变成单调不降，只要两数合法中间的数就一定能变得合法。考虑不改变的那些数，它们一定单调不降，所以答案就是序列总长度减去最长不下降子序列的长度。接下来看第二问，尝试观察一些性

原题是思路非常值得学习的一道题第一问：首先我们感性上觉得这题应该和LIS有一点关系，但里面有一点问题：1750505018如果我们求LIS的话，我们会认为只需要改掉505050即可，但其实我们只改掉这些数，我们是无法做到让数单增的我们发现这个限制写成数学语言即为：\(a_i-a_j\geq