首页 > 代码库 > UVa1471 Defense Lines (滑动窗口)

UVa1471 Defense Lines (滑动窗口)

2024-08-14 05:50:14   223人阅读

链接：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 (滑动窗口)


联系
我们