P9147 签到题 题解
syzf2222
·
·
题解
如果修改 a_i，最优的修改方案要么是令 a_i = a_{i+1}-1，要么是令 a_i = a_{i-1}+1。
那么就可以得到一个简单的 O(n^2) 做法，即枚举修改的位置，并计算答案。
预处理出未进行修改时，每个元素作为连续上升子序列的开头与结尾时的最长长度，记为 f_i,g_i。
如果存在 x 满足 a_{i+1}-1\ge x \ge a_{i-1}+1，那么可以进行合适的修改使得构造出长度为 g_{i-1}+1+f_{i+1} 的答案。
否则只能得到 g_{i-1}+1 或 f_{i+1}-1。扫一遍判断即可。复杂度 O(n)。