首页 > 代码库 > cf463d

cf463d

2024-07-21 22:21:58   218人阅读

这题说的是给了k个串算出这k个串的最长公共子序列，这k个串每个串都是由1--n的数字组成的。

将第一串的数字按照顺序重新编号为123...n 然后后面的串按照这个编号重新标号，就转化为下面每个串大最长递增子序列的问题，然后我们对于每个串计算出后面比他大的数然后建一条边（用邻接矩阵存）然后可以判断出从a到b点是否有k-1条这样我们专门挑那些k-1条的走这样保证每个序列中都有这样最后dfs算出最长的那个

#include <iostream>#include <cstdio>#include <string.h>using namespace std;const int MAX_N = 1009;int renum[MAX_N];int edg[MAX_N][MAX_N],dp[MAX_N];int rt[6][MAX_N],ans,R,n;bool use[MAX_N];void dfs(int loc, int len){       ans=max(len,ans);       dp[loc]=len;       for(int i=loc+1; i<=n; ++i)       if(edg[loc][i]==R&&dp[i]<len+1){         dfs(i,len+1);       }}int main(){     int k;     while(scanf("%d%d",&n,&k)==2){          for(int i =1; i<=n; ++i){              scanf("%d",&rt[0][i]);              renum[rt[0][i]]=i;          }          R=k-1;          for(int i=1; i<k; ++i){                rt[i][0]=0;               for(int j=1; j<=n; ++j){                scanf("%d",&rt[i][j]);                 rt[i][j]=renum[rt[i][j]];               }          }          memset(edg,0,sizeof(edg));          for(int i=1; i<k; i++){               for(int j =0; j<=n; ++j){                 for(int t=j+1; t<=n; ++t)                  if(rt[i][j]<rt[i][t]) edg[rt[i][j]][rt[i][t]]++;               }          }          ans=0;          memset(dp,0,sizeof(dp));          dfs(0,0);          printf("%d\n",ans);     }    return 0;}
View Code

 

cf463d


联系
我们