2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 The Heaviest Non-decreasing Subsequence Problem

Let $S$ be a sequence of integers $s_{1}$ , $s_{2}$ , $. . .$ , $s_{n}$ Each integer is is associated with a weight by the following rules:

(1) If is is negative, then its weight is $0$ .

(2) If is is greater than or equal to $10000$ , then its weight is $5$ . Furthermore, the real integer value of $s_{i}$ is $s_{i}-10000$ . For example, if $s_{i}$ 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 $s_{i1}$ , $s_{i2}$ , $. . .$ , $s_{ik}$ , with $i_{1}<i_{2} ... <i_{k}$ , such that, for all $1 \leq j < k$ , we have $s_{ij}<s_{ij+1}$ .

A heaviest non-decreasing subsequence of $S$ 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 $14$ 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: $s_{1}$ , $s_{2}$ , $. . .$ , $s_{n}$

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 亚洲区（南宁赛区）网络赛

最长上升子序列

由最长上升子序列可以想到思路，把权值为5的数分成五个权值为1的数，只需要把权值为5的数连写5个，这样就转化为求最长上升子序列的长度了。

先预处理，所有负数全部去掉，因为如果负数在序列前面，会使最长上升子序列的长度增加，然后把值大于等于10000的数减去10000，连写5次，求最长上升子列的长度即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e6+10;
int temp[MAXN],a[MAXN], c[MAXN], n;

int bin(int size, int k)
{
	int l = 1, r = size;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		if (k>=c[mid])   //升序
			l = mid + 1;
		else
			r = mid - 1;
	}
	return l;
}
int LIS()
{
	int i, j, cnt = 0, k;
	for (i = 1; i <= n; i++)
	{
		if (cnt == 0 || a[i]>=c[cnt])  //升序
			c[++cnt] = a[i];
		else
		{
			k = bin(cnt, a[i]);
			c[k] = a[i];
		}
	}
	return cnt;
}

int main()
{
//    freopen("in.txt","r",stdin);
	int t=1,i;
	while (scanf("%d", &temp[t++])!=EOF);
    n=t--;
    //预处理
    for(i=1,t=1;i<=n;i++)
    {
        if(temp[i]>=10000)
        {
            a[t++]=temp[i]-10000;
            a[t++]=temp[i]-10000;
            a[t++]=temp[i]-10000;
            a[t++]=temp[i]-10000;
            a[t++]=temp[i]-10000;
        }else if(temp[i]>=0)
            a[t++]=temp[i];
        else
            continue;
    }
    n=t--;
    int tem = LIS();
    cout<<tem<<endl;
    return 0;
}