51Nod 1294. 修改数组(贪心+最长不下降子序列) 日付: 11月 01, 2018 リンクを取得 Facebook × Pinterest メール 他のアプリ ## Problem 对数组$A$，可以随意修改，问最少修改几次使$A$严格递增，且每个数都是正整数。 数据范围：$1\le n \le 100000$ ## Solution 原数组中，因为严格递增，合法情况必定满足$A[j]\ge A[i]+j-i, \quad j>i$。如果将每个数转为$A[i]-i$后，这个合法条件就变成了非严格递增。先把小于0的去掉，对于剩下的数求出最长不下降子序列，就是最多的不用改的个数，最后用$n$减一下。 ## Code ```c++ #include <bits/stdc++.h> using namespace std; int main() { int n, x, len = 0; scanf("%d", &n); vector<int> Tmp(n + 1, INT_MAX); for (int i = 1; i <= n; i++) { scanf("%d", &x); if (x - i >= 0) { int p = upper_bound(Tmp.begin(), Tmp.end(), x - i) - Tmp.begin(); len = max(len, p + 1), Tmp[p] = x; } } printf("%d\n", n - len); return 0; } ``` コメント
コメント
コメントを投稿