首页 > 代码库 > CF 463D Gargari and Permutations [dp]
CF 463D Gargari and Permutations [dp]
给出一个长为n的数列的k个排列(1?≤?n?≤?1000; 2?≤?k?≤?5),求这个k个数列的最长公共子序列的长度
dp[i]=max{dp[j]+1,where j<i 且j,i对应的字符在k个排列中都保持相同的相对位置}
#include <iostream> #include <vector> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> using namespace std; #define pb push_back const int NN=2222; int f[7][NN]; int maxn; int anti[7][NN]; int dp[NN]; int main(){ #ifndef ONLINE_JUDGE freopen("/home/rainto96/in.txt","r",stdin); #endif int n,k;cin>>n>>k; for(int i=1;i<=k;i++) for(int j=1;j<=n;j++){ cin>>f[i][j]; anti[i][f[i][j]]=j; } for(int i=1;i<=n;i++){ for(int j=0;j<i;j++){ bool flag=false; for(int m=1;m<=k;m++) if(anti[m][f[1][i]]<anti[m][f[1][j]]) flag=true; if(flag) continue; dp[i]=max(dp[i],dp[j]+1); } maxn=max(maxn,dp[i]); } cout<<maxn<<endl; return 0; }
CF 463D Gargari and Permutations [dp]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。