首页 > 代码库 > HDOJ 5141 LIS again 二分

HDOJ 5141 LIS again 二分

2024-08-07 11:14:17   221人阅读


二分求LIS

对每一个位置为终点的LIS记录开头的最靠右边的值....

LIS again

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 272    Accepted Submission(s): 96


Problem Description
A numeric sequence of ai is ordered if a1<a2<…<aN. Let the subsequence of the given numeric sequence (a1,a2,…,aN) be any sequence (ai1,ai2,…,aiK), where 1≤i1<i2<…<iK≤N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, eg. (1, 7), (3, 4, 8) and many others. 
S[ i , j ] indicates ( ai,ai+1,ai+2,…,aj) .
Your program, when given the numeric sequence (a1,a2,…,aN), must find the number of pair ( i, j) which makes the length of the longest ordered subsequence of S[ i , j ] equals to the length of the longest ordered subsequence of (a1,a2,…,aN).
 

Input
Multi test cases (about 100), every case occupies two lines, the first line contain n, then second line contain n numbers a1,a2,…,aN separated by exact one space. 
Process to the end of file.

[Technical Specification]
1≤n≤100000
0≤ai≤1000000000
 

Output
For each case，.output the answer in a single line.
 

Sample Input
3
1 2 3
2
2 1
 

Sample Output
1
3
 

Source
BestCoder Round #21
 



#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long int LL;
const int maxn=100100;

int a[maxn],c[maxn],w[maxn],p[maxn],l[maxn];
int len,n;
LL ans;

void init()
{
	ans=0; len=0;
	memset(w,-1,sizeof(w));
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(int i=0;i<n;i++) scanf("%d",a+i);

		len=1; c[0]=a[0]; l[0]=1; p[0]=0; w[0]=0;

		for(int i=1;i<n;i++)
		{
			int j=lower_bound(c,c+len,a[i])-c;
			c[j]=a[i];

			if(j==0) w[j]=i;
			else w[j]=max(w[j],w[j-1]);

			p[i]=w[j];
			l[i]=j+1;

			if(j>=len) len++;
		}
		bool flag=false;
		int l1=-1;
		for(int i=0;i<n;i++)
		{
			if(l[i]==len)
			{
				flag=true;
				l1=max(l1,p[i]);
			}
			if(flag)
			{
				ans+=l1+1;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}


HDOJ 5141 LIS again 二分


联系
我们