[DP]Codeforces Round #264 (Div. 2) D

大致题意：

求多个数列(n=1000)的最长公共子串。

 

大致思路：

一开始没有头绪，后来发现一点，长度为n的数列中每个数都属于1--n且不重复，所以根据每个数列中每个数字的位置来判定即可。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,k,num[6][1003],mark[6][1003];
int dp[1003],res;
void dfs(int loc,int len){
    if(dp[loc]>=len)return;
    dp[loc]=len;
    res=max(res,len);
    int i,j;
    for(i=loc+1;i<=n;i++){
        bool flag=1;
        for(j=2;j<=k;j++){
            if(mark[j][num[1][i]]<mark[j][num[1][loc]]){
                flag=0;
            }
        }
        if(flag){
            dfs(i,len+1);
        }
    }
}
int main(){
    int i,j;
    while(scanf("%d%d",&n,&k)!=EOF){
        res=0;
        memset(dp,0,sizeof(dp));
        for(i=1;i<=k;i++){
            for(j=1;j<=n;j++){
                scanf("%d",&num[i][j]);
                mark[i][num[i][j]]=j;
            }
        }
        dfs(1,1);
        for(i=1;i<=n;i++){
            dfs(i,1);
        }
        cout<<res<<endl;
    }
    return 0;
}