The Heaviest Non-decreasing Subsequence Problem

Let SSS be a sequence of integers s1s_{1}s​1​​, s2s_{2}s​2​​, ………, sns_{n}s​n​​ Each integer is is associated with a weight by the following rules:

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

(2) If is is greater than or equal to 100001000010000, then its weight is 555. Furthermore, the real integer value of sis_{i}s​i​​ is si−10000s_{i}-10000s​i​​−10000 . For example, if sis_{i}s​i​​ is 101011010110101, then is is reset to 101101101 and its weight is 555.

(3) Otherwise, its weight is 111.

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

808080 757575 737373 939393 737373 737373 101011010110101 979797 −1-1−1 −1-1−1 114114114 −1-1−1 101131011310113 118118118

The heaviest non-decreasing subsequence of the sequence is <73,73,73,101,113,118><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 = 141+1+1+5+5+1=14. Therefore, your program should output 141414 in this example.

We guarantee that the length of the sequence does not exceed 2∗1052*10^{5}2∗10​5​​
Input Format

A list of integers separated by blanks:s1s_{1}s​1​​, s2s_{2}s​2​​,………,sns_{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 亚洲区（南宁赛区）网络赛
题意：一串数，小于0的weight 为-1，大于0小于10000的weight为1，大于10000的为5，求weight 最大的情况下的最长上升子序列。
大于10000的情况可以先转换即将这个值减去10000后，放入新数组中，放5次，因为它的weught=5，然后就得到一个新数组，求这个新数组的非递减最长子序列的长度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn=1000010;
int data[maxn];
int maxv[maxn];
int Find(int x,int len)
{
int mid,low=1,high=len;
while(low<=high)
{
mid=(low+high)>>1;
if(maxv[mid]<=x)
{
low=mid+1;
}
else high=mid-1;
}
return low;
}
int lis(int n)
{
int i,len=1;
maxv[1]=data[0];
for(i=1;i<n;i++)
{
if(data[i]>=maxv[len])
{
maxv[++len]=data[i];
}
else
{
int pos=Find(data[i],len);
maxv[pos]=data[i];
}
}
return len;
}
int main()
{
memset(data,0,sizeof(data));
memset(maxv,0,sizeof(maxv));
int len=0;
int x;
while(scanf("%d",&x)!=EOF)
{
if(x<0)
continue;
else if(x>=10000)
{
x=x-10000;
for(int j=0;j<5;j++)
data[len++]=x;
}
else
{
data[len++]=x;
}
}
printf("%dn",lis(len));
}

最后

以上就是善良钢笔最近收集整理的关于The Heaviest Non-decreasing Subsequence Problem的全部内容，更多相关The内容请搜索靠谱客的其他文章。