【CODEFORCES】 D. Gargari and Permutations

D. Gargari and Permutations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Gargari got bored to play with the bishops and now, after solving the problem about them, he is trying to do math homework. In a math book he have found k permutations. Each of them consists of numbers 1, 2, ..., n in some order. Now he should find the length of the longest common subsequence of these permutations. Can you help Gargari?
You can read about longest common subsequence there:https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
Input
The first line contains two integers n and k (1 ≤ n ≤ 1000; 2 ≤ k ≤ 5). Each of the next k lines contains integers 1, 2, ..., n in some order — description of the current permutation.
Output
Print the length of the longest common subsequence.
Sample test(s)
input

4 3
1 4 2 3
4 1 2 3
1 2 4 3

output

3

Note
The answer for the first test sample is subsequence [1, 2, 3].
문제풀이: 이 문제는 DAG로 풀 수 있다고 들었는데, 난 못해......
내 생각은 모든 수가 한 번밖에 나오지 않는 이상 나는 하나의 수조 S[I][J]로 I층의 수 J가 I+1층의 위치를 기록하고 D[I]로 A[I]로 끝날 때의 가장 긴 길이를 기록할 것이다.이를 통해 알 수 있듯이 모든 동일한 수를 연결하면 가장 긴 서열에 교차하는 선분이 존재하지 않기 때문에 우리는 점차적인 방정식을 얻을 수 있다.
D[I]=max(D[J]+1, D[I])(조건: 수 I의 연결선과 J의 연결선은 교차하지 않는다)
조건은 수조 S로 판단할 수 있는데, 이렇게 하면 이 문제는 '최장 하위 서열을 내려가지 않는다' 는 형상이 된다.마지막으로 D[I]의 최대치를 찾아내면 된다.

#include <iostream>
#include <cstdio>

using namespace std;

int s[10][1002],n,k,i,ans,j,a[7][1002],d[1002];
int _check(int i,int j)
{
    int de=1,x=i,y=j;
    while (s[de][a[de][x]]>s[de][a[de][y]] && de<k)
    {
        x=s[de][a[de][x]];
        y=s[de][a[de][y]];
        de++;
    }
    if (de==k) return 1;
    else return 0;
}

int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=k;i++)
        for (int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            s[i-1][a[i][j]]=j;
        }
    for (int i=1;i<=n;i++)  d[i]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<i;j++)
        if (_check(i,j)) d[i]=max(d[j]+1,d[i]);
    for (int i=1;i<=n;i++) ans=max(ans,d[i]);
    cout <<ans;
    return 0;
}