UVa 1471 Defense Lines——LIS nlogn 算法变形

UVa 1471 Defense Lines——LIS nlogn 算法变形

建议做这个题之前先学习一下LIS 的 nlogn 算法

注意二分查找时我们需要的是小于a【i】的数而不是等于甚至大于a【i】的数，当更新ans时发现貌似缺了1而无法理解代码时仔细考虑一下这一点

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 200000 + 10;int n, a[maxn], f[maxn], head[maxn], tail[maxn];int main(){ int T; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); if (n == 1) { printf("1\n"); continue; } head[n - 1] = tail[0] = 1; for (int i = n - 2; i >= 0; i--) { head[i] = (a[i] < a[i + 1]) ? head[i + 1] + 1 : 1; } for (int i = 1; i < n; i++) { tail[i] = (a[i] > a[i - 1]) ? tail[i - 1] + 1 : 1; } for (int i = 0; i <= n; i++) f[i] = INF; int ans = 0; for (int i = 0; i < n; i++) { int pos = lower_bound(f + 1, f + 1 + i + 1, a[i]) - (f + 1); ans = max(ans, pos + head[i]); f[tail[i]] = min(a[i], f[tail[i]]); } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。