Description
'Oh no, they've done it again', cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross
each other all over the place. At this late stage of the process, it is too
expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without rossing each other, is imminent. Bearing in mind that there may be housands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?
Figure 1. To the left: The two blocks' ports and their signal mapping (4,2,6,3,1,5). To the right: At most three signals may be routed on the silicon surface without crossing each other. The dashed signals must be bridged.
A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number pecifies which port on the right side should be connected to the i:th port on the left side.
Two signals cross if and only if the straight lines connecting the two ports of each pair do.
expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without rossing each other, is imminent. Bearing in mind that there may be housands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?
Figure 1. To the left: The two blocks' ports and their signal mapping (4,2,6,3,1,5). To the right: At most three signals may be routed on the silicon surface without crossing each other. The dashed signals must be bridged.
A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number pecifies which port on the right side should be connected to the i:th port on the left side.
Two signals cross if and only if the straight lines connecting the two ports of each pair do.
Input
On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer p<40000, the number of ports on the two functional blocks. Then
follow p lines, describing the signal mapping: On the i:th line is the port number of the block on the right side which should be connected to the i:th port of the block on the left side.
Output
For each test scenario, output one line containing the maximum number of signals which may be routed on the silicon surface without crossing each other.
Sample Input
4
6
4 2 6 3 1 5 10 2 3 4 5 6 7 8 9 10 1 8 8 7 6 5 4 3 2 1 9 5 8 9 2 3 1 7 4 6
Sample Output
3 9 1 4
题目大意：求严格递增序列的最大长度。
知识点： 摘自某个屌比
简述： LIS问题，即最长上升子序列问题，经典的解法有序列DP，通过这个算法，可以获得最长上升子序列的各种详细信息。但是，我们有时候只需要求最长上升子序列的长度，但是o(n^2)的时间复杂度太慢了，我们希望有一种算法，可以更快一点。 算法过程 既然动态规划太慢了，那么自然就想到了贪心。下述算法，就是运用了二分+贪心 首先考虑一个序列s：1、3、2、7、5、6、4 （一共7个数），另外一个辅助数组d，最终序列长度为ans 第1个数：d[1] = s[1] = 1 , ans = 1 ; 第2个数：s[2] > s[1] , 所以d[2] = s[2] , ans = 2 ; 第3个数：d[1] < s[3] < d[2] , 此时ans不改变，但是根据贪心法则，d[2] = s[3] ; 第4个数：s[4] > d[2]， d[3] = s[4] = 7 , ans = 3 ; 第5个数：s[5] < d[3] , ans不变，根据贪心法则，d[3] = s[5] ; 第6个数：s[6] > d[4] , d[4] = s[6] , ans =4 ; 第7个数：s[7] < d[4] , 为保证算法完整性，d[3] = s[7] （这里替代的数是第一个大于key的数）。 此时ans=4，d数组为：1、2、4、6 。 （如d[3]=4，意为有个队尾元素为4（最小的序列）的序列使得序列长度为3） 虽然我们算出了答案，但是我们并不能得到最终的最长子序列，这就是这个算法的不足。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int s[50001];
int d[50001];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&s[i]);
}
int len=1;
d[1]=s[1];
for(int i=2;i<=n;i++)
{
if(s[i]>d[len])
{
len++;
d[len]=s[i];
}
else
{
int l=1;
int r=len;
int mid;
int cut;
while(l<=r)
{
mid =(l+r)/2;
if(s[i]<d[mid])
{
cut=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
d[cut]=s[i];
}
}
printf("%d
",len);
}
return 0;
}