首页 > 代码库 > UVa1471 Defense Lines (滑动窗口)
UVa1471 Defense Lines (滑动窗口)
链接:http://bak.vjudge.net/problem/UVA-1471
分析:设g(i)为以第i个元素结尾的最长L序列长度,f(i)为以第i个元素开头的最长L序列长度,首先在O(n)时间内求出f(i)和g(i),枚举完j和i之后,最长L序列的长度就是g(j)+f(i)|j<i,A[j]<A[i]。
这样做的时间复杂度是O(n²)。还可以优化的更好,只枚举i,不枚举j,使用STL中的set,set容器可以看成是排好序的,而且自带lower_bound和upper_bound函数,把所有“有保留价值”的j按照A[j]从小到大排成一个有序表(用二元组(A(j),g(j))保存,以A[j]为关键字),维护g(j)根据A[j]严格单调递增,那么用二分查找找到满足A[j]<A[i]的最大的A[j],g(j)也是最大的。
每次枚举一个i,二分找到A[j]<A[i]最大的g(j)更新ans,接下来就是维护单增,如果g(j)>=g(i),准备要插入的二元组(A[i],g[i])肯定不是最优值,放弃将其插入有序表;否则将其插入有序表后,向前位置已经保证是单增的了,只需向后检查,删去肯定不是最优值的二元组,还有A[j]相同的j只保留最优的一个(虽然直接删掉旧的就可以过,但我没搞懂)。
1 #include <cstdio> 2 #include <set> 3 using namespace std; 4 5 const int maxn = 200000 + 5; 6 7 struct Candidate { 8 int a, g; 9 Candidate(int a, int g):a(a),g(g) {}10 bool operator < (const Candidate& rhs) const {11 return a < rhs.a;12 }13 };14 15 set<Candidate> s;16 int n, a[maxn], f[maxn], g[maxn];17 18 int main() {19 int T;20 scanf("%d", &T);21 while (T--) {22 scanf("%d", &n);23 for (int i = 1; i <= n; i++) scanf("%d", &a[i]);24 if (n == 1) { printf("1\n"); continue; }25 g[1] = 1;26 for (int i = 2; i <= n; i++)27 if (a[i - 1] < a[i]) g[i] = g[i - 1] + 1;28 else g[i] = 1;29 f[n] = 1;30 for (int i = n - 1; i >= 1; i--)31 if (a[i] < a[i + 1]) f[i] = f[i + 1] + 1;32 else f[i] = 1;33 s.clear();34 s.insert(Candidate(a[1], g[1]));35 int ans = 1;36 for (int i = 2; i <= n; i++) {37 Candidate c(a[i], g[i]);38 set<Candidate>::iterator it = s.lower_bound(c);39 bool keep = true;40 if (it != s.begin()) {41 Candidate last = *(--it);42 int len = f[i] + last.g;43 ans = max(ans, len);44 if (c.g <= last.g) keep = false;45 }46 if (keep) {47 ++it;48 if (it -> a == c.a && it -> g >= c.g) continue;49 s.erase(c);50 s.insert(c);51 it = s.find(c);52 it++;53 while (it != s.end() && it->a > c.a && it->g <= c.g) s.erase(it++);54 }55 }56 printf("%d\n", ans);57 }58 return 0;59 }
UVa1471 Defense Lines (滑动窗口)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。