要把序列变为先严格递增后严格递减的单峰序列,只能对任意位置做“+1”操作,且操作次数要最少。可以分三步:
令 b[j] 表示将原序列 a[1..j] 调整为严格递增时,第 j 个位置的最终值最小可能值;同时记录所需的操作次数前缀和 f[j]。
具体做法:
多多在纸上写下了一个整数序列,他可以对任意一个数进行 +1 操作,每个数的操作次数不限。
他想知道,他至少要操作多少次,可以使这个序列变成一个单峰序列。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.