本文主要是介绍从一列数中筛除尽可能少的数，使得从左往右看这些数是从小到大再从大到小，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题：从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。
解法：这是双端 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;
}
这篇关于从一列数中筛除尽可能少的数，使得从左往右看这些数是从小到大再从大到小的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
