2017 ACM-ICPC 亚洲区(南宁赛区)网络赛 The Heaviest Non-decreasing Subsequence Problem
Let SS be
a sequence of integers s_{1}s1, s_{2}s2, ......, s_{n}snEach
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}si is s_{i}-10000si−10000 .
For example, if s_{i}siis 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}si1, s_{i2}si2, ......, s_{ik}sik,
with i_{1}<i_{2}\
...\ <i_{k}i1<i2 ... <ik,
such that, for all 1
\leq j<k1≤j<k,
we have s_{ij}<s_{ij+1}sij<sij+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∗105
Input Format
A list of integers separated by blanks:s_{1}s1, s_{2}s2,......,s_{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
样例输出
14
题目来源
最长上升子序列
由最长上升子序列可以想到思路,把权值为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;
}
最新文章
- Mysql触发器示例
- [转]C++中四种类型转换符的总结
- J2SE宏观总结
- Android SharedPreferences使用以及原理详解
- Tomcat7出现HTTP Status 500 - java.lang.ClassCastException: org.apache.jasper.el.ELContextImpl cannot be cast to org.apache.jasper.el.ELContextImpl
- EF多表查询方式
- C#复习三(Day 22)
- margin属性的正负值确定
- python学习03-数据类型
- Hibernate学习(4)- Hibernate对象的生命周期
- Linux下安装部署Samba共享盘的操作手册
- Java容器解析系列(10) Map AbstractMap 详解
- 潭州课堂25班:Ph201805201 django框架 第九课 模型补充 博客小案例 (课堂笔记)
- Arcgis10.3在添加XY数据时出现问题
- 发行版Linux和麒麟操作系统下netperf 网络性能测试
- elementUI 通用确认框
- Netty核心概念(7)之Java线程池
- BZOJ1190_梦幻岛宝珠_KEY
- 八个常用的js正则表达式
- C#子线程中更新ui-----c# 多线程多文件批量下载
热门文章
- poj3440--Coin Toss(几何上的概率)
- 贝尔数--Codeforces908E. New Year and Entity Enumeration
- 【IntelliJ 】设置 IntelliJ IDEA 主题和字体的方法
- Reorder the Books-HDU5500
- P1605 迷宫 洛谷
- easyUi 学习笔记 (二 ) 使用tabs 里datagridview 发送ajax请求 不访问后台的问题
- Ubuntu 16.04安装WinRAR/7-Zip(基于CrossOver)
- C++虚函数表剖析
- 黑马day13 分页思路&;amp;实现
- HDU 4920(杭电多校训练#5 1010 题) Matrix multiplication(不知道该挂个什么帽子。。。)