问题:从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的(网易)。
解法:这是双端 LIS 问题,用 DP 的思想可解,目标规划函数
max{ b[i] + c[i] }, 其中 b[i] 为从左到右, 0 ~ i 个数之间满足递增的数字个数; c[i] 为从右到左, n-1 ~ i 个数之间满足递增的数字个数。最后结果为 n - max + 1。其中 DP 的时候,可以维护一个 inc[] 数组表示递增数字序列,inc[i] 为从小到大第 i 大的数字,然后在计算 b[i] c[i] 的时候使用二分查找在 inc[] 中找出区间 inc[0] ~ inc[i-1] 中小于 a[i] 的元素个数(low)。
源代码如下:
/**
* The problem:
* 从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的(网易)。
* use binary search, perhaps you should compile it with -std=c99
* fairywell 2011
*/
#include <stdio.h>
#define MAX_NUM (1U<<31)
int
main()
{
int i, n, low, high, mid, max;
printf("Input how many numbers there are: ");
scanf("%d/n", &n);
/* a[] holds the numbers, b[i] holds the number of increasing numbers
* from a[0] to a[i], c[i] holds the number of increasing numbers
* from a[n-1] to a[i]
* inc[] holds the increasing numbers
* VLA needs c99 features, compile with -stc=c99
*/
double a[n], b[n], c[n], inc[n];
printf("Please input the numbers:/n");
for (i = 0; i < n; ++i) scanf("%lf", &a[i]);
// update array b from left to right
for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM;
//b[0] = 0;
for (i = 0; i < n; ++i) {
low = 0; high = i;
while (low < high) {
mid = low + (high-low)*0.5;
if (inc[mid] < a[i]) low = mid + 1;
else high = mid;
}
b[i] = low + 1;
inc[low] = a[i];
}
// update array c from right to left
for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM;
//c[0] = 0;
for (i = n-1; i >= 0; --i) {
low = 0; high = i;
while (low < high) {
mid = low + (high-low)*0.5;
if (inc[mid] < a[i]) low = mid + 1;
else high = mid;
}
c[i] = low + 1;
inc[low] = a[i];
}
max = 0;
for (i = 0; i < n; ++i )
if (b[i]+c[i] > max) max = b[i] + c[i];
printf("%d number(s) should be erased at least./n", n+1-max);
return 0;
}
分享到:
相关推荐
针对胶囊内窥镜检查的海量图像数据, 提出基于归一化互信息量及归一化互相关系数的冗余图像数据筛除方法。将图像在HSV色彩空间量化聚类; 然后计算相邻图像的相似度系数, 最后根据相似筛除比例进行迭代筛除。针对49例...
一种新型种子生产输送振动筛除杂装置的制作方法.docx
在构建VGI数据爬取模型(VDCM)和地名本体的基础上, 针对从VGI数据中提取地名信息过程中出现的地名geo/geo歧义(多个地理位置对应同一地名)、地名与经纬度匹配错误、多个资源对应同一地名等问题提出相应的解决方案...
通过对山西8号煤层5个不同煤级的微量元素富集程度和元素酸脱除率的统计对比,发现,受岩浆热力烘烤作用影响的煤的变质程度对煤中微量元素的富集个数、富集程度和赋存形态影响甚大。总的趋势是,煤变质程度愈大,富集元素...
此网络采用PointCNN网络中的X卷积通过4次卷积提取点云数据进行空间特征, 尽可能的保留了异物目标的空间信息, 提高检测准确度. 通过对采集的数据进行测试实验, 本文设计的方法能够准确地识别出异物与非平整路面, ...
筛除异常数据matlab代码HPO2GO v1.1 人类表型本体 (HPO) 和基因本体 (GO) 术语之间的映射,用于预测基因/蛋白质 - 功能 - 表型 - 疾病关联。 引文 如果您发现 HPO2GO 有用,请考虑引用此出版物: 多安,T.(2018 年...
方便集成可限制最大输入字符串的textfield/textview,并具备具备显示剩余输入字数,筛除emoji表情,自动设置换行返回,获取光标位置,设置光标位置的功能。
我们经常会将数据源放在DataTable里面,但是有时候也需要移除不想要...上面就是如何Datatable中某一行的id为99,就移除这一行,id为字段名 以上代码简单实现了c# datatable 删除某一行的实现方法,希望对大家有所帮助!
php利用imap类对邮件进行操作。显示邮件列表,显示邮件正文,可显示附件,可转换标题正文乱码。
针对可见光图像和红外图像的匹配问题,提出一种基于边缘信息的Harris-SIFT匹配算法。匹配过程中,对红外图像进行Retinex边缘增强,再分别对可见光图像和处理后的红外图像进行双边滤波预处理,以增强两类图像边缘结构...
Goldbach问题的筛函数按整数类别分割法,宋富高,,Goldbach问题中的所有筛法都要求筛除所有合数,虽然严格说那是不必要的,何况筛除所有合数一般是非常困难的. 本文引入的一种新的方�
unscented kalman filtering程序:包含函数和一个demon。程序包括五个步骤:参数计算、sigma点集计算、时间更新、观测更新、滤波更新。每一步都有详细的注释。以供学习参考。
Goldbach问题的三种解决方案,宋富高,,术语“命题 {1, b}”指每一个大偶数N都可以表为一个素数与一个不超过b个素因子的乘积之和. Goldbach问题中的筛法总是要求筛除每一个合�
Goldbach问题的筛函数按区间分割法,宋富高,,术语“命题{1, b}”意指每一个大偶数N 都可以表示为一个素数与一个至多b个素数的乘积之和. Goldbach问题中的所有筛法都要求筛除所有合�
采用无信息变量消除法(UVE)对变量进行筛选,筛选出最重要的变量信息。
C#中发送广播消息的过程如下,注意要调用SetSockOption函数,不然要抛出异常: Socket sock = new Socket(AddressFamily.InterNetwork, SocketType.Dgram, ProtocolType.Udp); IPEndPoint iep1 = new IPEndPoint...
筛除测量过程中产生的无效数据,确定有效搜索区域并在该区域内进行全局遍历,找到最优定位坐标,解决了求解值不是全局最优的问题。同时,为了进一步提高定位精度,采取了适当增加参考节点数量的措施。实验结果表明,...
# 通过正则表达式筛除string中的标点符号 def clearn_str(string): # 筛除掉中文标点 string = re.sub(r'["#$%&'()*+,-/:;<=>@[\]^_`{|}~⦅⦆「」、 、〃〈〉《》「」『』【】〔〕...