[UVa] 111 - History Grading

The main thing about this problem is not in the fact that you have to know some extraordinary algo thingy, it's simply LCS but with a twist. The problem statement clearly says that the input will be the ranks of the incidents.

1 point for each event whose rank matches its correct rank

So, what you you actually get isn't the real sequence. It's a sequence which you should use to make the sequence you want. Modify every given sequence (incl. the main one) in the following manner.

Suppose 2 1 3 5 6 4
It is 2 1 3 6 4 5

The sequence is telling you to put the positions in the directed places.

2 is 1st so 1 goes 2nd
1 is 2nd so 2 goes 1st
3 is 3rd so 3 stays 3rd
5 is 4th so 4 goes 5th
6 is 5th so 5 goes sixth
4 is 6th so 6 goes 4th

Now when the sequences are prepared, run LCS on it an voila!!

#include "stdio.h"

int max(int a, int b) {
    if (a>=b) return a;
    else return b;
}
int main() {

    int i, j, n_evt, q, temp;
    int seq_main[22], pro[22], c[22][22];

    scanf("%d",&n_evt);

    for (i=0 ; i&n_evt ; i++) {
        scanf("%d",&temp);
        seq_main[temp-1]=i+1;
    }

    while (scanf("%d",&temp)==1) {
        pro[temp-1]=1;
        for (q=1 ; q<n_evt ; q++) {
            scanf("%d",&temp);
            pro[temp-1]=q+1;
        }

        for (i=0 ; i<=n_evt ; i++) {
            c[i][0] = c[0][i] = 0;
        }

        for (i=1 ; i<=n_evt ; i++) {
            for (j=1 ; j<=n_evt ; j++) {
                if (seq_main[i-1]==pro[j-1]) {
                    c[i][j] = c[i-1][j-1] + 1;
                } else {
                    c[i][j] = max(c[i-1][j],c[i][j-1]);
                }
            }
        }

        printf("%d\n",c[n_evt][n_evt]);

        i=j=q=0;

    }

    return 0;

}