POJ 1631 - Bridging signals ( LIS )
题意
有p条线路,它们有可能相交。现在让你去掉一些线路,使得剩下的线不相交且线最多 ( p < 40000 )
思路
为使得连线不相交, 必须选择一个上升的连接序列, 而求剩下的线不相交且最多就是求LIS ( 最长上升子序列 )
由于p最大达40000, 1000 ms 肯定不能用复杂度为O(n*n)的朴素动态规划,会超时。这时考虑用O(nlogn)的 二分+贪心
建一个dp数组,dp[i]表示长度为i的LIS结尾元素的最小值。贪心策略:对于一个上升子序列,显然其结尾元素越小,越有利于在后面接其他的元素,也就越可能变得更长。因此,我们只需要维护dp数组,对于每一个a[i],如果a[i] > len[当前最长的LIS长度],就把a[i]接到当前最长的LIS后面,即dp[++当前最长的LIS长度]=a[i]。
关于维护dp数组 :
对于每一个a[i],如果a[i]能接到LIS后面,就接上去;否则,就用a[i]取更新dp数组。具体方法是,在dp数组中找到第一个大于等于a[i]的元素dp[j],用a[i]去更新dp[j]。如果从头到尾扫一遍dp数组的话,时间复杂度仍是O(n^2)。我们注意到dp数组内部一定是单调不降的,所有我们可以二分dp数组,找出第一个大于等于a[i]的元素。二分一次dp数组的时间复杂度的O(logn),所以总的时间复杂度是O(nlogn)。
目前为止看到过的最易理解的LIS – O(nlogn)算法分析:
最长上升子序列(LIS)长度的O(nlogn)算法
AC代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 40000+5;
const int INF = 0x3f3f3f3f;
int dp[maxn], a[maxn];
int main()
{
int T, n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for( int i = 0; i < n; i++ )
scanf("%d",&a[i]);
int len = 1;
for( int i = 0; i < n; i++ ){
int p = lower_bound(dp, dp+len, a[i]) - dp;
dp[p] = a[i];
if( p == len ) len++;
}
printf("%d\n",len-1);
}
return 0;
}
上一篇: 题目:动态规划(1)
下一篇: Less实战(二):变量
推荐阅读
-
[POJ](1631)Bridging signals ---- LIS+O(nlogn)优化(二分)
-
Bridging signals ————LIS模板
-
Bridging signals (POJ 1631 HDU 1950)
-
POJ 1631 - Bridging signals ( LIS )
-
B - Bridging signals 【poj 1631 lis dp】
-
POJ1631 Bridging signals
-
poj 1631 Bridging signals
-
D - Bridging signals POJ - 1631
-
D - Bridging signals POJ - 1631
-
POJ 1631 Bridging signals