【校内训练】Increasing
求最少改变几个数,使得序列变成最长上升子序列。
【题解】
可以修改的条件:$a_j-a_i \leq j-i (j<i)$ 即 $a_j-j \leq a_i-i$,那么把$a_i$变为$a_i-i$即可。
然后套用求LIS的nlogn方法。
# include <stdio.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; int f[100010]; int n, a[100010], c[100010]; int main() { scanf("%d", &n); for (int i=1; i<=n; ++i) { scanf("%d", &a[i]); a[i] = a[i] - i; } f[1] = 1; // 这是普通的 O(n^2) 做法 /* for (int i=2; i<=n; ++i) for (int j=1; j<i; ++j) if(f[j]+1 > f[i] && a[i] >= a[j]) f[i] = f[j]+1; */ a[n+1] = 2147483647; int ans = 1; c[1] = 1; for (int i=2; i<=n; ++i) c[i] = n+1; for (int i=2; i<=n; ++i) { int l=1, r=ans, anst = 0; while(1) { if(r-l<=3) { for (int j=r; j>=l; --j) if (a[c[j]] <= a[i]) { anst = c[j]; break; } break; } int mid = l+r>>1; if(a[c[mid]] <= a[i]) l = mid; else r = mid; } f[i] = f[anst] + 1; if(a[c[f[i]]] > a[i]) c[f[i]] = i; ans = max(ans, f[i]); } printf("%d\n", n-ans); return 0; }