ACM: 111 – History Grading

這一題即是稍做變化的Longest Increasing Subsequence (LIS)問題，但要注意的是input資料。input資料是Event的Order:

Event: 1 2 3 4 5 6 7 8 9 10
Order: 3 1 2 4 9 5 10 6 8 7

即是Event by Order是: 2, 3, 1, 4, 6, 8, 10, 9, 5, 7。學生的回答也需要做如此的調整，比對出來才是正確的解答。原本沒有搞清楚，就想不通為什麼sample output跟自己算的答案不一樣了！

REFERENCE

Longest Increasing Subsequence

CODE

#include <stdio.h>

#define MAX 20

int main(){
  int i, j, t;
  int n, c[MAX+1], r[MAX+1], lis[MAX+1], max;
  
  scanf("%d", &n);
  
  /*Read Correct Order*/
  for(i=1; i<=n; i++)
    scanf("%d", &c[i]);
    
  /*Read Student Response*/
  while( scanf("%d", &t) != EOF){
    r[t] = 1;
    max = lis[1] = 1;
    for(i=2; i<=n; i++){
      scanf("%d", &t);
      r[t] = i;
      lis[i] = 1;
    }
    
    for(i=2; i<=n; i++){
      for(j=1; j<i; j++)
        if( c[ r[i] ] > c[ r[j] ] )
          if( lis[i] < (lis[j] + 1) )
            lis[i] = lis[j] + 1;
      
      if( max < lis[i] )
        max = lis[i];
    }/*i*/
       
    printf("%d\n", max);
  }/*while*/

  exit(0);
}