首页 > 试题广场 > Array
[编程题]Array

小红有两个长度为n的排列AB。每个排列由[1,n]数组成,且里面的数字都是不同的。

现在要找到一个新的序列C,要求这个新序列中任意两个位置(i,j)满足:

如果在A数组中C[i]这个数在C[j]的后面,那么在B数组中需要C[i]这个数在C[j]的前面。

请问C序列的长度最长为多少呢?


输入描述:
第一行一个整数,表示N。

第二行N个整数,表示A序列。

第三行N个整数,表示B序列。

满足:N<=50000


输出描述:
输出最大的长度
示例1

输入

5
1 2 4 3 5
5 2 3 4 1

输出

4

说明

最长的C为1,3,4,5
python动态规划之抱头痛哭...
上面的图是我的二维dp,超内存。
思路:把b逆序,求a和b的最长公共子序列,转化为经典动规。
下面的图是[小二郎求offer]的一维dp,超时。
思路:tmp存储a和b的关系,即b的元素在a中的位置。


编辑于 2019-08-20 16:42:17 回复(0)

Python

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

tmp = []
for i in range(n):
    tmp.append(a.index(b[i]))
dp = [1] * (n)
for i in range(1,n):
    for j in range(i):
        if tmp[i]<tmp[j]:
            dp[i] = max(dp[j]+1, dp[i])
print(max(dp))


发表于 2019-08-19 10:01:39 回复(8)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

map<int ,int> mp;

struct node{
    int num;
    int rank;
}arr[50007];
int in[50007];

int main() {
    int n, num;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) 
        scanf("%d", &arr[i].num);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num);
        mp[num] = i + 1;
    }
    for (int i = 0; i < n; ++i) arr[i].rank = - mp[arr[i].num];

    in[0] = arr[0].rank;
    int len = 1;
    for (int i = 1; i < n; ++i) {
        int adr = lower_bound(in, in + len, arr[i].rank) - in;
        if (len == adr) in[len ++] = arr[i].rank;
        else in[adr] = arr[i].rank;
    }
    printf("%d\n", len);
    return 0;
}

思路:你仔细看看、想想就会知道其实这是一个最长下降子序列。我已开始就是想着吧最左边的1挪到最右边,那么肯定是满足条件的了,但是这样依赖,挪到右边之后的位置的右边假设还有数,那么这些数就废了,那么问题就是怎么挪哪些数到右边的时候尽量保证废了的数字尽量的少,那么你就按照下面的顺序给上面的数赋值顺序,你就会发现变成了最长下降子序列...

you see you see one day day的

发表于 2019-08-03 01:03:01 回复(0)
N = int(input())
list1 = list(map(int,input().split()))
list2 = list(map(int,input().split()))
 
list3 = [list1.index(i) for i in list2]
#list3.reverse()
dp = [0 for i in range(N)]
size = 0
for x in list3:
    i,j = 0,size
    while i != j:
        m = (i+j)//2
        if dp[m] > x:
            i = m + 1
        else:
            j = m
    dp[i] = x
    size = max(size,i+1)
print(size)
python貌似最多通过百分之50,时间复杂度nlogn。就是最长递减子序列问题
发表于 2019-08-15 13:57:35 回复(1)
这题妙啊、
发表于 2019-08-12 20:44:11 回复(0)