http://acm.timus.ru/problem.aspx?space=1&num=1651
题目大意： 
   有向图由含有n个结点的链表给出，每个链表结点由一个数字表示，相邻两链表结点表示有向图中一条有向边(i-1指向i)，,现要求该链的一条子链，满足以下三个条件： 
   1.子链的起点跟终点分别跟原链相等。 
   2.子链中边的顺序与原链相等；即，原链中边p比边q晚出现的话，子链中边p不能比边q早出现。 
   3.求满足上述条件的最短子链。
原链长度不超过100000， 结点数字在[1~10000]范围内。 

Sample Input
9
1 2 7 3 2 8 4 8 5
Sample Output
1 2 8 5

      我的想法是直接从左向右扫一遍，O(n)复杂度。
      主要思路：依次从左向右扫描，分情况处理，并在处理时记录终点的最小值，以及位置。
            1. 假设当前位置i上的结点没有被扩展过，那么当前位置的距离值（到起始结点）cost[i] = cost[i - 1] + t; （t任意正值）
                同时记录当前结点的cost值，以及当前位置的前驱位置。并将当前结点标记为已扩展。
            2. 假设当前位置i上的结点已被扩展过，且当前结点的cost大于前一位置的cost值 + t，那么当前位置的距离值（到起始结点）cost[i] = cost[i - 1] + t; （t任意正值）， 同时更新当前结点的cost值，以及当前位置的前驱位置。
            3. 假设当前位置i上的结点已被扩展过，且当前结点的cost小于等于前一位置的cost值 + t，那么当前位置的距离值（到起始结点）cost[i] = 当前结点的cost， 同时记录当前位置的前驱位置。（注意：此时前驱位置为当前结点最后一次更新时的位置的前驱）；

eg:
位置: 
         1   2   3   4   5   6   7   8   9
位置上的结点值:
         1   2   7   3   2   8   4   8   5
cost:   
         1   2   3   4   2   3   4   3   4
前驱位置:
         0   1   2   3   1   5   6   5   8

Code:

#include<cstdio>
#include<cstdlib>

int Q[100001];
int pre[100001];
int cost[100001];
int lastPos[10001];
int check[10001];
int ans[10001];
int minD;
int I;
int nq;
int na;

inline int nextInt(){
      char ch = getchar();
      int x = 0;
      while(ch < '0' || ch > '9'){
         ch = getchar();
      }
      while(ch >= '0' && ch <= '9'){
            x = x * 10 + ch - 48;
            ch = getchar();
      }
      return x;
}

int main(int argc, char* argv[], char* env[])
{
      int i = 0;
      int end = 0;
      while(scanf("%d", &nq) != EOF){
            for(i = 0; i < 100001; i++){
                  pre[i] = 0;
                  if(i < 10001){
                        check[i] = 0;
                        lastPos[i] = 0;
                  }
            }
            for(i = 1; i <= nq; i++){
                  Q[i] = nextInt();
            }
            end = Q[nq];
            cost[0] = 0;
            minD = 100011;
            for(i = 1; i <= nq; i++){
                  if(!check[Q[i]] || cost[i - 1] + 1 < check[Q[i]]){
                        cost[i] = cost[i - 1] + 1;
                        check[Q[i]] = cost[i];
                        pre[i] = i - 1;
                  }
                  else{
                        cost[i] = check[Q[i]];
                        pre[i] = pre[lastPos[Q[i]]];
                  }
                  lastPos[Q[i]] = i;
                  if(Q[i] == end && cost[i] < minD){
                        minD = cost[i];
                        I = i;
                  }
            }
            na = 0;
            ans[na++] = end;
            I = pre[I];
            while(I){
                  ans[na++] = Q[I];
                  I = pre[I];
            }
            for(i = na - 1; i >= 0; i--){
                  if(i != na - 1){
                        printf(" ");
                  }
                  printf("%d", ans[i]);
            }
            printf("\n");
      }
      return 0;
}