vijos1264:神秘的咒语

描述

身为拜月教的高级间谍，你的任务总是逼迫你出生入死。比如这一次，拜月教主就派你跟踪赵灵儿一行，潜入试炼窟底。

据说试炼窟底藏着五行法术的最高法术：风神，雷神，雪妖，火神，山神的咒语。为了习得这些法术，要付出艰辛的努力，但是回报同样十分丰厚。

拜月希望你告诉他咒语的长度为多少。（你：“请问您想知道咒语的具体内容吗？”拜月：“想，但是vijos不支持special judge。”-_-原来大人物也有大人物的悲哀。。。）
于是你偷偷躲在一边，想乘机看看咒语究竟是什么。突然，天空（？？试炼窟底看的到天空？？）出现了两条非常长的数字串，你抓狂了。究竟哪个才是真正的咒语呢？你突然想到，这两个都不是咒语（不妨称之为伪咒语），而真正的咒语却与他们有着密切的联系。于是你打开拜月亲手给你写的纸条："The Real Incantation is Their Common Increasing Subsequence of Maximal Possible Length"
"该死的拜月，居然还会E文!"你咒骂着，但为了一家老小的生命，又不得不卖命地算着咒语的长度。

格式

输入格式

第一行为1个数N,代表有N组测试数据。

对于每组测试数据，描述了两条数字串，首先一个数字为一条伪咒语的长度M，接下来M个数描述了伪咒语的内容。

输出格式

共N行，每行一个数字，描叙了对应咒语的长度。

样例输入：

1
5 1 4 2 5 -12
4 -12 1 2 4

样例输出：

思路：公共最长上升子序列。

#include <iostream>

#include <string.h>

using namespace std;

typedef long long ll;

const int MAXN=;

int n,m;

ll a[MAXN],b[MAXN];

int dp[MAXN];

int main()

{

    int T;

    cin>>T;

    while(T--)

    {

        memset(dp,,sizeof(dp));

        cin>>n;

        for(int i=;i<n;i++)

            cin>>a[i];

        cin>>m;

        for(int i=;i<m;i++)

            cin>>b[i];

        int res=;

        for(int i=;i<n;i++)

        {

            int mx=;

            for(int j=;j<m;j++)

            {

                if(b[j]<a[i])    mx=max(mx,dp[j]);

                if(b[j]==a[i])    dp[j]=mx+;

                res=max(res,dp[j]);

            }

        }

        cout<<res<<endl;

    }

    return ;

}

巴特西

vijos1264:神秘的咒语

描述

格式

输入格式

输出格式

最新文章

热门文章