【NOIP模拟赛】Incr

2014年10月30日1,3950

【题目描述】

数列 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