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

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

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

(2) If is is greater than or equal to 1000010000,
then its weight is 55.
Furthermore, the real integer value of s_{i}s​i​​ is s_{i}-10000s​i​​−10000 .
For example, if s_{i}s​i​​is 1010110101,
then is is reset to 101101 and
its weight is 55.

(3) Otherwise, its weight is 11.

A non-decreasing subsequence of SS is
a subsequence s_{i1}s​i1​​, s_{i2}s​i2​​, ......, s_{ik}s​ik​​,
with i_{1}<i_{2}\
...\ <i_{k}i​1​​<i​2​​ ... <i​k​​,
such that, for all 1
\leq j<k1≤j<k,
we have s_{ij}<s_{ij+1}s​ij​​<s​ij+1​​.

A heaviest non-decreasing subsequence of SSis
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:

8080 7575 7373 9393 7373 7373 1010110101 9797 -1−1 -1−1 114114 -1−11011310113 118118

The heaviest non-decreasing subsequence of the sequence is <73,
73, 73, 101, 113, 118><73,73,73,101,113,118> with
the total weight being 1+1+1+5+5+1
= 141+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}2∗10​5​​

Input Format

A list of integers separated by blanks:s_{1}s​1​​, s_{2}s​2​​,......,s_{n}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

样例输出

14

题目来源

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;

}

2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 The Heaviest Non-decreasing Subsequence Problem的相关教程结束。