The Heaviest Non-decreasing Subsequence Problem

Let $s1s_{1}s1, s2s_{2}s2, ........., sns_{n}sn Each integer is is associated with a weight by the following rules:$

(1) If is is negative, then its weight is

(2) If is is greater than or equal to $sis_{i}si is si−10000s_{i}-10000si−10000 . For example, if sis_{i}si is 101011010110101, then is is reset to 101101101 and its weight is 555.$

(3) Otherwise, its weight is

A non-decreasing subsequence of $si1s_{i1}si1, si2s_{i2}si2, ........., siks_{ik}sik, with i1<i2 ... <iki_{1}<i_{2} ... <i_{k}i1<i2 ... <ik, such that, for all 1≤j<k1 leq j<k1≤j<k, we have sij<sij+1s_{ij}<s_{ij+1}sij<sij+1.$

A heaviest non-decreasing subsequence of

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:

The heaviest non-decreasing subsequence of the sequence is

We guarantee that the length of the sequence does not exceed $2∗1052*10^{5}2∗105$

Input Format

A list of integers separated by blanks: $s1s_{1}s1, s2s_{2}s2,.........,sns_{n}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

样例输出

题目来源

2017 ACM-ICPC 亚洲区（南宁赛区）网络赛、

求最长曾序列，dp

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int N = 2e5+10;
 5 int a[N*5], dp[N*5];
 6 int main() {
 7     int n, num = 0;
 8     while(scanf("%d", &n) != EOF) {
 9         if(n >= 10000) {
10             for(int i = 0; i < 5; i ++) a[num++] = n - 10000;
11         } else if(n >= 0) a[num++] = n;
12     }
13     for(int i = 0; i <= N*5; i ++) dp[i] = 1000000;
14     for(int i = 0; i < num; i ++) {
15         *upper_bound(dp, dp+num, a[i]) = a[i];
16     }
17     cout << lower_bound(dp,dp+num,1000000)-dp << endl ;
18     return 0;
19 }