【校内训练】Increasing
求最少改变几个数，使得序列变成最长上升子序列。
【题解】
可以修改的条件：aj−ai≤j−i(j<i) 即 aj−j≤ai−i，那么把ai变为ai−i即可。
然后套用求LIS的nlogn方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | # 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;} |
2023年4月20日 19:40
Our team is made up of professional writers and citizen journalists with a wide range of journalism interests who are passionate about reporting Education Updates with transparency in the general public interest.ekhan is a group of ekhan.in professional writers who have banded together to provide devoted news coverage of current events in India. Our team is made up of professional writers and citizen journalists with a wide range of journalism interests who are passionate about reporting Education Updates with transparency in the general public interest.