D. Gargari and Permutations
題意:k個串,分别是1~n的某種排列,輸出k個串的最長公共子序列。
思路:如果像兩個串那樣dp求LCS複雜度是O(n^k),是不行的。如果先求兩個串的LCS,再和下一個串求LCS,直到最後一個串,也是不行的,因為兩個串的LCS可能是多解的。我的方法是對每個串,如果串中i在j前面,就建一條邊,然後對k個圖進行與運算,合成一個圖,再對這個圖求最長路。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h>
#define INF 1000000010
#define ll long long
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 1000
using namespace std;
int num[6][1010];
int dp[1010];
bool m[6][1010][1010];
int n,K;
int dfs(int x){
if(dp[x]!=-1)return dp[x];
bool flag=false;
for(int i=1;i<=n;i++){
if(m[0][x][i]){
dp[x]=max(dp[x],dfs(i)+1);
flag=true;
}
}
if(!flag){
dp[x]=1;
return 1;
}
return dp[x];
}
int main(){
while(cin>>n>>K){
memset(dp,-1,sizeof(dp));
for(int i=1;i<=K;i++){
for(int j=1;j<=n;j++){
cin>>num[i][j];
}
}
for(int k=1;k<=K;k++){
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
m[k][num[k][i]][num[k][j]]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
m[0][i][j]=1;
for(int k=1;k<=K;k++){
m[0][i][j]&=m[k][i][j];
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,dfs(i));
}
cout<<ans<<endl;
}
return 0;
}