「NOIP模拟赛」Incr

2014年10月30日1,7400

「题目描述」

数列 A1,A2,…,AN,修改最少的数字,使得数列严格单调递增。

「输入格式」

第 1 行,1 个整数 N

第 2 行,N 个整数 A1,A2,…,AN

「输出格式」

1 个整数,表示最少修改的数字

「样例输入」

3

1 3 2

「样例输出」

1

「数据范围」

对于 50% 的数据,N ≤ 10^3

对于 100% 的数据,1 ≤ N ≤ 10^5,1 ≤ Ai ≤ 10^9

题解

暴力可以用f[i][j]表示前i个最后一个改为j的方案

ai减去下标求最长上升子序列ans。。。答案是n-ans

 

说点什么

提醒
avatar