111 - History Grading

 1 #include<iostream>
 2 using namespace std;
 3 int numevents[21];
 4 int d[21]; //假设状态为d，即按照学生提供的事件顺序（不是他的那串输入数字），d[i]表示第i个数字能够达到的最长序列
 5 int path[21];
 6 int temp[21];
 7 int maxdis;
 8 int n;
 9 int dis(int start){
10     if(d[start]>-1)
11         return d[start];
12     
13     for(int i=start+1;i<=n;i++){
14         if(numevents[path[start]]<numevents[path[i]])
15             if(d[start]<1+dis(i))
16                 d[start]=1+dis(i);
17     }
18     if(d[start]>-1)
19         return d[start];
20     d[start]=1;
21     return d[start];
22 }
23 int main(){
24     int m;
25     cin>>n;
26     for(int i=1;i<=n;i++){
27         cin>>m;
28         numevents[i]=m;
29     }
30     while(cin>>m){
31         path[m]=1;
32         d[1]=-1;
33         for(int i=2;i<=n;i++){
34             cin>>m;
35             path[m]=i;
36             d[i]=-1;
37         }
38         maxdis=0;
39         for(int i=1;i<=n;i++){
40             if(maxdis<dis(i))
41                 maxdis=dis(i);
42         }
43         cout<<maxdis<<endl;
44     }
45 }