UVa 481 What Goes Up

解題：LIS演算法(印出最後出現的LIS)

Code：

 1  #include<stdio.h>

 2  #include<stdlib.h>

 3  #include<iostream>

 4  #include<algorithm>

 5  #include<vector>

 6  using namespace std;

 7  vector<int> v;

 8  int LIS(vector<int> &s,vector<int> &pos)

 9  {

10      if(s.size()==0) return 0;

11      v.push_back(s[0]);

12      pos[0]=0;

13      for(int i=1;i<s.size();i++)

14      {

15          int n=s[i];

16          if(n>v.back())

17          {

18              v.push_back(n);

19              pos[i]=v.size()-1;

20          }

21          else

22          {          

23              auto it=lower_bound(v.begin(), v.end(), n);

24              *it=n;

25              pos[i]=it-v.begin();           

26          }

27      }

28      return v.size();

29  }

30  vector<int> forprint;

31  void Print(int ans,int k, vector<int> &pos,vector<int> &s)

32  {

33      if(ans<0) return;

34      for(int i=k; i>=0; i--)

35      {

36          if(pos[i]==ans-1)

37          {

38              forprint.push_back(s[i]);

39              Print(ans-1,i-1,pos,s);

40              return;

41          }

42      }

43  }

44  int main()

45  {

46      vector<int> s;

47      int n;

48      while(scanf("%d",&n)!=EOF) s.push_back(n);

49      vector<int> pos(s.size());

50      int ans=LIS(s,pos);

51      cout<<ans<<endl;

52      printf("-\n");

53      Print(ans,s.size()-1,pos,s);

54      for(int i=forprint.size()-1;i>=0;i--) cout<<forprint[i]<<endl;

55      return 0;

56  }

57