uva 111 A History Grading

 1 /*
 2 lis变形 ，一开始没看出来，看了别人的解题报告才看出来
 3 题意：
 4    求相对位置，不变的最长序列
 5 
 6 
 7 */
 8 
 9 #include<stdio.h>
10 const int N=100;
11 int a[N],dp[N],rank[N];
12 int  max(int x,int y)
13 {
14     if(x>y)return x;
15     else return y;
16 }
17 int main()
18 {
19     int n,i,j,k;
20     scanf("%d",&n);
21     for(i=1;i<=n;i++)
22     {
23          scanf("%d",&k); 
24          rank[i]=k;
25     }
26     while(scanf("%d",&k)!=EOF)
27     {
28         a[k]=rank[1];
29         for(i=2;i<=n;i++)
30          {
31              scanf("%d",&k);
32              a[k]=rank[i];
33          }
34 
35           int ans=-1;
36          for(i=1;i<=n;i++)
37          {
38              dp[i]=1;
39              for(j=i-1;j>=1;j--)
40              {
41                  if(a[i]>a[j])
42                  dp[i]=max(dp[i],dp[j]+1);
43              }
44              ans=max(ans,dp[i]);
45 
46          }
47          printf("%d\n",ans);
48     }
49 
50 }