//#if defined(__GNUC__)
//#warning "This is a deprecated opencv header provided for compatibility. Please include a header from a corresponding opencv module"
//#endif

#include "opencv2/core/core_c.h"
#include "opencv2/core/core.hpp"

#endif

      实际上编译被跳转了，但是回到 \vs2008\inlcude目录下，惊讶的发现生成的结果事实上未包含 opencv文件夹！此时如果仅仅把 ...\vs2008\include\opencv2配置，则vs2008仍然无法导入头文件，此时需要手动将 \include\opencv 目录复制到 \vs2008下，然后追加配置 ...\vs2008\include\opencv。最后F5编译，bingo~

   上面这条表达式出来之后就很容易想到LIS了，也就是枚举ai和ai+1的位置，然后左半部分和又半部分分别往相反的方向做LIS，求出出列数最短的一个中点即可，其中做LIS可以采用二分查找，使得转移花费从O(n)降为O(lg n)。
 

 1#include<cstdio>
 2#include<cstring>
 3#define inf 0x7fffffff
 4#define N 1001
 5#define MAX(a,b) (a<b)?b:a
 6#define MIN(a,b) (a<b)?a:b
 7using namespace std;
 8int lis[N],lds[N];
 9double w[N];
10
11int find(double c[],int len,double k){
12    int left=0,right=len,mid=(left+right)/2;
13    while(left<=right){
14        if( k>c[mid] ) left=mid+1;
15        else if( k<c[mid] ) right=mid-1;
16            else { return mid; }
17        mid=(left+right)/2;
18    }
19    return left;
20}
21
22int main(){
23    int n,i,j,res;
24    int tmpDp[N];
25    double c[N];
26    while(scanf("%d",&n)!=EOF){
27        for(i=0;i<n;i++) scanf("%lf",&w[i]);
28        
29        for(i=0;i<=n;i++) c[i]=inf;
30        c[0]=-1; c[1]=w[n-1];
31        memset(tmpDp,0,sizeof(tmpDp));
32        tmpDp[n-1]=1;
33        for(i=n-2;i>-1;--i){
34            j=find(c,n+1,w[i]);
35            c[j]=w[i]; tmpDp[i]=j;
36        }
37        for(j=-1,i=n-1;i>-1;--i){ j=MAX(j,tmpDp[i]); lds[i]=j; }
38        
39        for(i=0;i<=n;i++) c[i]=inf;
40        c[0]=-1; c[1]=w[0];
41        memset(tmpDp,0,sizeof(tmpDp));
42        tmpDp[0]=1;
43        for(i=1;i<n;++i){
44            j=find(c,n+1,w[i]);
45            c[j]=w[i]; tmpDp[i]=j;
46        }
47        for(j=-1,i=0;i<n;++i){ j=MAX(j,tmpDp[i]); lis[i]=j; }
48
49        res=inf;
50        for(i=0;i<n;++i){
51            res=MIN(res,n-(lis[i]+lds[i+1]));
52        }
53        printf("%d\n",res);
54    }
55    return 0;
56}

　 这是SCC问题的第一个算法，由Tarjan于1972年提出。算法仍然借助DFS，但它并不依靠遍历顺序来把不同的SCC分离到不同的DFS树中，而是让多个SCC并存于同一个DFS树中，用某种手段把他们分开。考虑一个强分量C，设其中第一个被发现的点为x，由白路径定理，C中其他点都是x的后代。我们希望在x访问完成时立刻输出C。(注意这里是一个严格的数学描述)。这样，就可以在同一棵DFS树中区分开所有的SCC了。因此问题的关键是：如何判断一个点是否为SCC中最先被发现的点。
　
　   如图。假设我们正在判断u是否为某SCC中第一个被发现的节点。如果我们发现从u的儿子出发可以到达u的祖先w,显然u\v\w在同一个SCC中，因此u不是该SCC第一个被发现的节点。如果从v出现最多只能到u，那么u是该SCC中第一个被发现的节点（也许有同学会问，若所有子节点不能到达u本身，何以能说明u是和子树强联通的？其实由于DFS的特点，若这样的情况出现，实际上在u的子树上已经完成了一个强分量的寻找，u此时是只到它本身的“第一个”被发现节点，原书的描述是严格和归纳的）。这样，问题转化为求：一个点u最远能到达的祖先的d值。注意这里的“到达”可以通过后向边或交叉边，但是前提是只能通过栈里面的点而不是已经确定SCC编号的其他点。图中实线表示一条边，虚线表示一条或多条边。


      定义low[u]为u及其后代能追溯到的最早祖先v的发现时间戳pre[v]，我们可以在计算low函数的同时完成SCC的计算，low函数的递推方法如下：
      利用全局栈_sta保存当前SCC中的节点（注意栈中节点形成树而不一定是链），cnt为开发当前点u的时间戳，scnt为强分量编号器，id[]为强分量编号数组。

      原始的Tarjan算法递推方式为：如果 pre[w]<pre[u]且w在栈中，则low[u]=min{pre[w],low[u]}，注意后一个限制是为了保证w不是在另一个已经发现的SCC中。下面的代码更简洁，在标记强分量后，只需要将low[w]设为最大值，表明它不再是任何点的祖先，那么w就不会被其他强分量吸收了，想想为什么。

 1void dfs-scc(int u){
 2    int w,min;
 3    min=low[u]=pre[u]=cnt++;
 4     /**//* 初始化时间戳，low值，子节点最小祖先 为当前时间戳 */
 5     _sta.push(u);
 6     
 7     for each (u,w){
 8         if(pre[w]==-1) dfs-scc(w);
 9         /**//* 未开发节点 */
10         if( low[w]<min ) min=low[w];
11         /**//* 求出u所有儿子i最远能到达的祖先 */
12     }
13     
14     if(min<low[u]){ low[u]=min; return ; }
15     /**//* 所有的儿子能到达的最远祖先是u的祖先，因此u不是SCC
16         第一个被发现的节点，通过子节点，u应能到达这样的第一个节点 */
17     do{
18         w=_sta.pop(w);
19         id[w]=scant;
20         low[w]=0x7fffffff; /**//* 锁定low，保证w不会被其他强分量吸收 */
21     }while(w!=u)
22     /**//* 此时，u的所有子节点必能且最远仅能到达u，他们沟通构成一个SCC */
23     scant++;
24}