2017 icpc 南宁赛区 L.The Heaviest Non-decreasing Subsequence Problem（LIS）

96 阅读 0 评论 64 点赞

我是靠谱客的博主激昂砖头，最近开发中收集的这篇文章主要介绍2017 icpc 南宁赛区 L.The Heaviest Non-decreasing Subsequence Problem（LIS），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

【题解】

这题比较水，注意点细节就好，输入的时候把数据处理好，输入完直接操作就好。

【AC代码】

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<deque>
#include<algorithm>
#define ll long long
#define INF 1008611111
#define M (t[k].l+t[k].r)/2
#define lson k*2
#define rson k*2+1
using namespace std;
const int N =1e6+5;
int
a[N], f[N], d[N];
// f[i]用于记录 a[0...i]的最大长度
int bsearch(const int *f, int size, const int &a)
{
int
l=0, r=size-1;
while( l <= r )
{
int
mid = (l+r)>>1;
if( a >= d[mid-1] && a < d[mid] )
return mid;
// >&&<= 换为: >= && <
else if( a <d[mid] )
r = mid-1;
else l = mid+1;
}
}
int LIS(const int *a, const int &n)
{
int
i, j, size = 1;
d[0] = a[0]; f[0] = 1;
for( i=1; i < n; ++i )
{
if( a[i] < d[0] )
// <= 换为: <
j = 0;
else if( a[i] >= d[size-1] ) // > 换为: >=
j = size++;
else
j = bsearch(d, size, a[i]);
d[j] = a[i]; f[i] = j+1;
}
return size;
}
int main()
{
int i,j,ans=0,d;
while(scanf("%d",&d)!=EOF)
{
if(d<0)
continue;
if(d>=10000)
{
for(i=0;i<5;i++)
{
a[ans]=d%10000;
ans++;
}
}
else
{
a[ans]=d;
ans++;
}
}
printf("%dn",LIS(a,ans));
return 0;
}