ACM 111 History Grading

LCS，輸入格式要看清楚


#include <stdio.h>

int main(void)
{
    int i, j, n, s1[21], s2[21], lcs[21][21];
   
    scanf("%d", &n);
   
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &j);
        s1[j] = i;
    }
   
    while (scanf("%d", &j) == 1)
    {
        s2[j] = 1;
        for (i = 2; i <= n; i++)
        {
            scanf("%d", &j);
            s2[j] = i;
        }
       
        // LCS
        for (i = 0; i <= n; i++)
            lcs[i][0] = lcs[0][i] = 0;
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                if (s1[i] == s2[j])
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                else
                    lcs[i][j] = (lcs[i-1][j]>lcs[i][j-1])?lcs[i-1][j]:lcs[i][j-1];
       
        printf("%d\n", lcs[n][n]);
    }
   
    return 0;
}