本文共 3108 字，大约阅读时间需要 10 分钟。
题意：给你一个1-n不重复的 k个排列，让你求最长公共子序列
解题思路：
1）拓扑排序 + DP 这里可以知道，最长公共子序列必须满足里面 前后的字母 必须在任意一个序列里面都保持前后关系，所以我们可以把前后关系看成一条边。那么问题就装换成了在 有向无环图中求 最长路 ，这个问题可以用拓扑排序来解决。
代码：
1 // File Name: 463b.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月10日 星期二 08时28分49秒 4 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #include 25 #define LL long long26 27 using namespace std;28 int dp[6][1005][1005];29 int a[1005];30 vector mp[1005];31 int vis[1005];32 int ans[1005];33 int mx = 0 ; 34 int ru[1005];35 int n, k ;36 queue qu;37 void solve()38 {39 memset(vis,0,sizeof(vis));40 for(int i = 1;i <= n;i ++)41 {42 if(ru[i] == 0)43 {44 qu.push(i);45 }46 }47 while(!qu.empty())48 {49 int tmp = qu.front();50 qu.pop();51 //printf("%d\n",tmp);52 for(int i = 0 ;i < mp[tmp].size();i ++)53 {54 ru[mp[tmp][i]]--;55 //printf("%d %d\n",mp[tmp][i],ru[mp[tmp][i]]);56 ans[mp[tmp][i]] = max(ans[tmp]+1,ans[mp[tmp][i]]);57 if(ru[mp[tmp][i]] == 0)58 {59 qu.push(mp[tmp][i]);60 }61 }62 mx = max(mx,ans[tmp]);63 }64 }65 int main(){66 scanf("%d %d",&n,&k);67 for(int i = 1;i <= k;i ++)68 {69 for(int j = 1;j <= n;j ++)70 {71 scanf("%d",&a[j]);72 for(int s = 1; s < j ;s ++)73 {74 dp[i][a[s]][a[j]] = 1;75 }76 }77 }78 for(int i = 1;i <= n;i ++)79 {80 for(int j = 1;j <= n;j ++)81 {82 dp[0][i][j] = dp[1][i][j];83 for(int s = 2; s <= k ;s ++)84 {85 dp[0][i][j] = dp[0][i][j] & dp[s][i][j];86 }87 if(dp[0][i][j] == 1)88 {89 ru[j] ++ ; 90 mp[i].push_back(j);91 }92 }93 }94 solve();95 printf("%d\n",mx+1);96 return 0;97 }
2）知道了所有的前后关系以后，再对任意一个序列进行dp，dp[i] 表示 以i结尾的最长上升子序列的长度
1 // File Name: 463b.cpp 2 // Author: darkdream 3 // Created Time: 2015年03月10日 星期二 08时28分49秒 4 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #include 25 #define LL long long26 27 using namespace std;28 int dp[6][1005][1005];29 int ans[1005];30 int a[1005];31 int n , k ; 32 int main(){33 scanf("%d %d",&n,&k);34 for(int i = 1;i <= k;i ++)35 {36 for(int j = 1;j <= n;j ++)37 {38 scanf("%d",&a[j]);39 for(int s = 1; s < j ;s ++)40 {41 dp[i][a[s]][a[j]] = 1;42 }43 }44 }45 for(int i = 1;i <= n;i ++)46 {47 for(int j = 1;j <= n;j ++)48 {49 dp[0][i][j] = dp[1][i][j];50 for(int s = 2; s <= k ;s ++)51 {52 dp[0][i][j] = dp[0][i][j] & dp[s][i][j];53 }54 }55 }56 int mx = 1 ; 57 for(int i = 1;i <= n;i ++)58 {59 ans[i] = 1 ; 60 int tmp = a[i];61 for(int j = 1;j < i ;j ++)62 {63 if(dp[0][a[j]][tmp])64 {65 ans[i] = max(ans[i],ans[j]+1);66 }67 mx = max(mx,ans[i]);68 }69 }70 printf("%d\n",mx);71 return 0;72 }
转载于:https://www.cnblogs.com/zyue/p/4326220.html
