Posted on 2009-08-24 20:00
Uriel 閱讀(419)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ 、
DP
兩次LIS,用O(nlogn)的算法才能過(guò)，搞了很久，以前一直是O(n^2)做的
/**//*Problem: 3670 User: Uriel
Memory: 744K Time: 47MS
Language: C++ Result: Accepted*/
#include<stdio.h>
#include<stdlib.h>
int b[30010],i,j,a[30010],t,n,len,lex,c[30010],size1,size2,f[30010],g[30010];
int BS1(int k)
{
int s,e,m;
s=0;
e=size1-1;
while(s<=e)
{
m=(s+e)/2;
if(k>=b[m-1] && k<b[m])return m;
else if(b[m]>k)e=m-1;
else
s=m+1;
}
}
int BS2(int k)
{
int s,e,m;
s=0;
e=size2-1;
while(s<=e)
{
m=(s+e)/2;
if(k<=c[m-1] && k>c[m])return m;
else if(c[m]<k)e=m-1;
else
s=m+1;
}
}
int min(int a,int b)
{
return a<=b?a:b;
}
int main()
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
j=0;
b[0]=a[0];
f[0]=1;
size1=1;
for(i=1;i<n;i++)
{
if(a[i]<b[0])j=0;
else if(a[i]>=b[size1-1])j=size1++;
else
j=BS1(a[i]);
b[j]=a[i];
f[i]=j+1;
}
j=0;
c[0]=a[0];
g[0]=1;
size2=1;
for(i=1;i<n;i++)
{
if(a[i]>c[0])j=0;
else if(a[i]<=c[size2-1])j=size2++;
else j=BS2(a[i]);
c[j]=a[i];
g[i]=j+1;
}
printf("%d\n",min(n-size2,n-size1));
system("PAUSE");
return 0;
}