首页 > 代码库 > Codeforces 463D. Gargari and Permutations【DP】

Codeforces 463D. Gargari and Permutations【DP】

2024-07-20 10:34:39   221人阅读

题目大意：

给出1~n的k个排列（2<=k<=5），要求其中的最长公共子序列。

做法：

算是不难的DP，dp[i]表示以i为结尾的最长公共子序列的长度，由于每个数在一个排列中只可能出现一次，我们用一个二维数组pos[i][j]表示数字j在第i行出现在第几个位置，再用一个数组cnt[i] 记录i出现了多少次；当第i个数出现了k次之后，说明能够以该数为结尾构成公共子序列，那么dp[i]=max(dp[j]+1)，其中i，j满足pos[u][i]>pos[u][j](1<=u<=k)；当然，为了节约时间，我们可以把之前已经计算过的dp[i]值的下标存到vector里面，这样只需要遍历这个vector找出符合条件的数即可.

代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define N 1010
using namespace std;
int pos[6][N],cnt[N],a[6][N],dp[N];
vector<int> q;
int main()
{
    int n,k,ans=0;
    scanf("%d%d",&n,&k);
    for(int i=0;i<k;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&a[i][j]);
    for(int i=0;i<n;i++)
        for(int j=0;j<k;j++){
            int cur=a[j][i];
            pos[j][cur]=i;
            cnt[cur]++;
            if(cnt[cur]==k){
                if(q.size()==0) dp[cur]=1;
                else for(int kk=0;kk<q.size();kk++){
                        bool flag=false;
                        for(int l=0;l<k;l++)
                            if(pos[l][cur]<pos[l][q[kk]]) {flag=true;break;}
                        if(!flag) dp[cur]=max(dp[cur],dp[q[kk]]+1);
                        else dp[cur]=max(dp[cur],1);
                    }
                ans=max(ans,dp[cur]);
                q.push_back(a[j][i]);
            }
        }
    cout<<ans<<endl;
    return 0;
}


Codeforces 463D. Gargari and Permutations【DP】


联系
我们