p2501
解题报告P2501 [HAOI2006] 数字序列
P2501 [HAOI2006] 数字序列 题目描述 现在我们有一个长度为 \(n\) 的整数序列 \(a\)。但是它太不好看了,于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。 输入格式 第一行是一个整数,表示序列长度 \(n\)。 第二行有 \(n\) ......
P2501 [HAOI2006] 数字序列
先来看第一问。 发现直接做要考虑两数中间的数能否变得合法,所以按套路将 \(a_i\) 减去 \(i\),这样就只要变成单调不降,只要两数合法中间的数就一定能变得合法。考虑不改变的那些数,它们一定单调不降,所以答案就是序列总长度减去最长不下降子序列的长度。 接下来看第二问,尝试观察一些性质: 可能有 ......