唯要注意
Given the correct chronological order of n events 1, 2, 3, ... , n
as c1, c2, c3, ... , cn where 1 <= ci <= n denotes the ranking of event i in the correct chronological order。
表示位置本身是事件,
而數字的意義是發生的次序先後。
好比1 4 5 3 2表示
事件1第1個發生,
事件2第4個發生,
事件3第5個發生,
事件4第3個發生,
事件5第2個發生;
而非第1個發生的是事件1,
第2個發生的是事件4,
第3個發生的是事件5,
第4個發生的是事件3,
第5個發生的是事件2。
反過來想就對啦!
/* ACM 111 History Grading * mythnc * 2012/01/09 16:13:15 * run time: 0.016 */ #include <stdio.h> #define MAXN 21 #define TRUE 1 #define FALSE 0 #define MAX(X, Y) (X >= Y ? X : Y) int input(int *, int); void lcs(int *, int *, int); int list[MAXN][MAXN]; int main(void) { int n; int correct[MAXN], test[MAXN]; scanf("%d", &n); input(correct, n); while (input(test, n)) { lcs(correct, test, n); printf("%d\n", list[n][n]); } return 0; } /* input: receive input data */ int input(int *seq, int n) { int i, pos; /* start from [1] to save data */ for (i = 1; i <= n; i++) { if (scanf("%d", &pos) != 1) return FALSE; seq[pos] = i; } return TRUE; } /* lcs: use dp to find longest length */ void lcs(int *s1, int *s2, int n) { int i, j; /* set list[x][0] and list[0][x] to zero */ for (i = 0; i <= n; i++) list[i][0] = list[0][i] = 0; /* i, j is equal to e1, e2 */ for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) if (s1[i] == s2[j]) /* e1 = e2: do LCS(sub1, sub2) + e1 */ list[i][j] = list[i - 1][j - 1] + 1; /* + 1 mean e1 */ else /* e1 != e2: do max(LCS(sub1, s2), sub2(s1, sub2)) */ list[i][j] = MAX(list[i - 1][j], list[i][j - 1]); }
沒有留言:
張貼留言