学步园

最近学习DP，做到最长XX序列的nlogn算法时，感到十分纠结。上网看了诸多文章，发现其实都是“互相借鉴”。

为了搞懂，我花了好几天，主要研究二分怎么写，最后总算大彻大悟了！

以下代码是NOIP拦截导弹的代码，求XX序列的模块我写成了函数，并且添加了详细的注释。

creativewang原创,转载请写出处。不要把我名字和EMAIL删掉==||

/**<br /> 最长XX序列，nlogn实现。C语言。<br /> email:creativewang@163.com<br /> **/<br /> #include<stdio.h><br /> #define LEN 1010</p> <p>int s[LEN],x[LEN],n;</p> <p>int increase(int n) /**<- 最长上升序列,我尽量说清楚，因为本人在这个问题上纠结了很长时间， */<br /> { /**<- 网上的我没看懂，所以自己研究了一下，希望你明白，不再纠结^_^ */<br /> x[0]=1; /**<- x[0]存储了x[]的长度 */<br /> x[1]=s[1]; /**<- x[n]存储长度为n的序列的尾数，可以知道它是严格单增的 */<br /> int x1,x2,mid,i;</p> <p> for(i=2;i<=n;i++)<br /> {<br /> x1=1;<br /> x2=x[0];<br /> if(x[1]>s[i]) /**<- s[i]小于所有的尾数，所以它目前只能构成长度为1的序列 */<br /> x[1]=s[i]; /**<- 并且我们此时要更新x[1],以保留更小的允许的尾数 */<br /> else if(x[x[0]]<s[i]) /**<- s[i]大于所有尾数，所以把它接在最长的序列的后面 */<br /> x[++x[0]]=s[i]; /**<- 并修改x[]的长度 */<br /> else /**<- 二分搜索，看了网上的代码，我很纠结==！*/<br /> { /**<- 我们的目的：找到最大的pos，使其满足s[i]>x[pos] */<br /> while(x1<=x2)<br /> {<br /> mid=x1+(x2-x1)/2;<br /> if(s[i]>x[mid]) /**<- s[i]大于区间的中点，所以pos的最大值应在[mid,x2],注意x[]单增 */<br /> x1=mid+1; /**<- 调整直至s[i]<=x[x1],此时x1在要求的pos的右侧，即pos=x1-1,因为最后一次调整时x[mid]<s[i]<=x[mid+1] */<br /> else /**<- 不大于的情况,即s[i]<=x[mid]，在左半边区间寻找*/<br /> x2=mid-1;<br /> }<br /> if(s[i]<x[x1]) /**<- 最终的pos是x1-1, */<br /> x[x1]=s[i]; /**<- 更新，这个很好理解 */<br /> }<br /> }<br /> return x[0];<br /> }</p> <p>int nIncrease(int n) /**<-最长不升子序列，not increase...,原理和上面差不多 */<br /> {<br /> x[0]=1;<br /> x[1]=s[1];<br /> int x1,x2,mid,i;<br /> for(i=2;i<=n;i++)<br /> {<br /> if(s[i]>x[1])<br /> x[1]=s[i];<br /> else if(s[i]<=x[x[0]])<br /> x[++x[0]]=s[i];<br /> else<br /> {<br /> x1=1;<br /> x2=x[0];<br /> while(x1<=x2)<br /> {<br /> mid=x1+(x2-x1)/2;<br /> if(s[i]<=x[mid])<br /> x1=mid+1;<br /> else<br /> x2=mid-1;<br /> }<br /> if(s[i]>x[x1])<br /> x[x1]=s[i];<br /> }<br /> }<br /> return x[0];<br /> }</p> <p>int main(void)<br /> {<br /> int i;<br /> scanf("%d",&n);<br /> for(i=1;i<=n;i++)<br /> scanf("%d",s+i);</p> <p> printf("%d %d/n",nIncrease(n),increase(n));</p> <p> return 0;<br /> }<br /> /*在RQNOJ上AC，如果把[]换成*，可能会快一点*/<br />