bit space namespace max icp pan for lowbit n)
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<cmath>
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 200005;
- const int maxm = 800005;
- int h[maxm], num[maxn];
- int n, m;
- int lowbit(int x)
- {
- return x & (-x);
- }
- void update(int x)
- {
- while (x <= n)
- {
- h[x] = num[x];
- for (int i = 1; i < lowbit(x); i <<= 1)
- {
- h[x] = max(h[x], h[x - i]);
- }
- x += lowbit(x);
- }
- return ;
- }
- int findans(int begin, int end)
- {
- int ans = 0;
- while (end >= begin)
- {
- ans = max(ans, num[end]);
- end--;
- for (; end - lowbit(end) >= begin; end -= lowbit(end))
- {
- ans = max(ans, h[end]);
- }
- }
- return ans;
- }
- int main()
- {
- n=200005;
- int ans = -1;
- int teshu = 0;
- int now;
- memset(h, 0, sizeof(h));
- while (scanf("%d", &now) != EOF)
- {
- if (now < 0)
- {
- continue;
- }
- if (now >= 10000)
- {
- now %= 10000;
- if (now == 0)
- {
- teshu += 5;
- }
- else
- {
- int cur = max(findans(1, now), teshu) + 5;
- ans = max(ans, cur);
- num[now] = cur;
- update(now);
- }
- }
- else
- {
- if (now == 0)
- {
- teshu += 5;
- }
- else
- {
- int cur = max(findans(1, now), teshu) + 1;
- ans = max(ans, cur);
- num[now] = cur;
- update(now);
- }
- }
- }
- cout<<ans<<endl;
- return 0;
- }
2017 ICPC 南宁 L 带权最值费递减序列
来源: http://www.bubuko.com/infodetail-2324006.html