UVa 111 History Grading

Code：

 1  #include<stdio.h>

 2  #include<stdlib.h>

 3  #include<iostream>

 4  #include<algorithm>

 5  #include<map>

 6  #include<vector>

 7  #include<sstream>

 8  using namespace std;

 9  int lis(vector<int> &s)

10  {

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

12      vector<int> v;

13      vector<int> idx(s.size());

14      v.push_back(s[0]);

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

16      {

17          int n=s[i];

18          if(n>v.back())

19          {

20              v.push_back(n);

21              idx[i]=v.size()-1;

22          }

23          else

24          {

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

26              *it=n;

27              idx[i]=it-v.begin();

28          }

29      }

30      return v.size();

31 

32  }

33  int main()

34  {

35      map<int,int> ma;

36      int n,ans[25]= {0},ans1[25]={0};

37      cin>>n;

38      for(int i=1; i<=n; i++)

39      {

40          cin>>ans[i];

41          ans1[ans[i]-1]=i;

42      }

43      for(int i=0;i<n;i++) ma[ans1[i]]=i;

44      string str,line;

45      getline(cin,line);

46      while(getline(cin,str))

47      {

48          int ind=0;

49          stringstream ss(str);

50          int tmpq[25]= {0},q[25]={0},tt[25]={0};

51          int x;

52          while(ss>>x) tmpq[ind++]=x;

53          for(int i=1;i<=n;i++)

54          {

55              tt[tmpq[i-1]-1]=i;

56 

57          }

58          for(int i=0;i<n;i++) q[i]=ma[tt[i]];

59          vector<int> s(q,q+n);

60          int fans=lis(s);

61          cout<<fans<<endl;

62      }

63      return 0;

64  }