我是靠谱客的博主 炙热日记本,这篇文章主要介绍The Heaviest Non-decreasing Subsequence Problem 2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 常见问题,现在分享给大家,希望可以做个参考。

本来是个裸的线段树的题

但是把负数删掉,权重为5 的点,赋值5遍放到队列里

这样问题就转化成了求最长上升(非下降)子序列

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <set> #include <queue> #include <algorithm> #include <vector> #include <cctype> #include <stack> #include <sstream> #include <list> #include <map> #include <assert.h> #define debug() puts("************") #define MS(a,b) memset(a,b,sizeof a) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> P; //const int INF = 0x3f3f3f3f; const double inf = 1e20; const double PI = 3.1415926535; const double eps = 1e-9; const LL mod = 1e9+7; const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1}; const int maxn = 1000000 + 7; const LL INF = 0x3f3f3f3f3f3f3f3f; LL b[maxn]; vector<LL> vec; int main() { LL x; while(~scanf("%lld", &x)) { if(x < 0) continue; else if(x >= 10000) { x -= 10000; for(int i = 0; i < 5; ++i) vec.push_back(x); //cnt++; } else { vec.push_back(x);//cnt++; } } int n = vec.size(); //for(int i = 0; i < n; ++i) // cout << vec[i] << " "; memset(b, INF, sizeof b); for(int i = 0; i < n; ++i) { //if(a[i] < 0) *upper_bound(b, b+n, vec[i]) = vec[i]; } int ans = lower_bound(b, b+n, INF) - b; cout << ans << endl; return 0; } /* 80 75 73 93 73 73 10101 97 -1 -1 114 -1 10113 118 */


最后

以上就是炙热日记本最近收集整理的关于The Heaviest Non-decreasing Subsequence Problem 2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 常见问题的全部内容,更多相关The内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(91)

评论列表共有 0 条评论

立即
投稿
返回
顶部