本文主要是介绍ACM-ICPC 2017 南宁赛区网络预赛 L The Heaviest Non-decreasing Subsequence Problem 【最长非递减子序列的变形】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 1000ms
- 131072K
Let S be a sequence of integers s1, s2, ......, sn Each integer is associated with a weight by the following rules:
(1) If is negative, then its weight is 0.
(2) If is greater than or equal to 10000, then its weight is 5. Furthermore, the real integer value of si is -10000. For example, if si is 10101, then is is reset to 101 and its weight is 5.
(3) Otherwise, its weight is 1.
A non-decreasing subsequence of S is a subsequence si1, si2, ......,sik, with i1<i2 ... <ik, such that, for all 1≤j<k, we have sij<sij+1.
A heaviest non-decreasing subsequence of SS is a non-decreasing subsequence with the maximum sum of weights.
Write a program that reads a sequence of integers, and outputs the weight of its
heaviest non-decreasing subsequence. For example, given the following sequence:
80 75 73 93 73 73 10101 97 −1 −1 114 −1 10113 118
The heaviest non-decreasing subsequence of the sequence is <73, 73, 73, 101, 113, 118>with the total weight being 1+1+1+5+5+1 = 14. Therefore, your program should output 1414 in this example.
We guarantee that the length of the sequence does not exceed 2∗10^5
Input Format
A list of integers separated by blanks:s1, s2,......,sn
Output Format
A positive integer that is the weight of the heaviest non-decreasing subsequence.
样例输入
80 75 73 93 73 73 10101 97 -1 -1 114 -1 10113 118样例输出
14题目来源
2017 ACM-ICPC 亚洲区（南宁赛区）网络赛
题目大意：给定一个整数序列，每个整数有一个权值，负数的权值为0，大于等于10000的数要减去10000，其权值为5，其他数的权值为1。问这个整数序列的最长非降子序列中权值最大为多少
题解：最长非降子序列的变形，由于权值不大，因此把权值5的数重复5次，把权值为0的负数忽略，这样答案就是新整数序列的最长非降子序列，就可以使用O（nlogn）的算法。
程序说明：upper_bound(q1,q2,x)函数返回有序区间 [q1,q2)中第一个大于x的数的迭代器，如果没有则返回q2。程序没有存储元素，这样更节省内存
AC的C++代码：
#include<iostream>
#include<algorithm>using namespace std;const int N=200005;
int b[N],len;int main()
{int x,n;while(scanf("%d",&x)!=EOF){n=1;if(x<0)continue;else if(x>=10000){x-=10000;n=5; }for(int i=1;i<=n;i++){if(len==0||x>=b[len-1])b[len++]=x;else{int k=upper_bound(b,b+len,x)-b; b[k]=x;}}}printf("%d\n",len);return 0;
}
这篇关于ACM-ICPC 2017 南宁赛区网络预赛 L The Heaviest Non-decreasing Subsequence Problem 【最长非递减子序列的变形】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
