问题 22544 --Modified LCS

22544: Modified LCS

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

LCS stands for longest common subsequence, and it is a well known problem. A sequence in this problem
means a list of integers, and a sequence X is considered a subsequence of another sequence Y, when the
sequence X can be obtained by deleting zero or more elements from the sequence Y without changing the
order of the remaining elements.
In this problem you are given two sequences and your task is to nd the length of the longest sequence
which is a subsequence of both the given sequences.
You are not given the sequences themselves. For each sequence you are given three integersN, FandD,
whereNis the length of the sequence, Fis the rst element in the sequence. Each element except the
rst element is greater than the element before it byD.
For exampleN= 5,F= 3 andD= 4 represents the following sequence: [3, 7, 11, 15, 19].
There will be at least one integer which belongs to both sequences and it is not greater than 1,000,000.

输入

Your program will be tested on one or more test cases. The rst line of the input will be a single integer
T, the number of test cases (1 <=T<=100). Followed by the test cases, each test case is described in

one line which contains 6 integers separated by a single spaceN1 F1 D1 N2 F2 D2(1<=N1,N2<=10^18

and (1<= F1,D1,F2,D2<=10^9) representing the length of the rst sequence, the rst element in

the rst sequence, the incremental value of the rst sequence, the length of the second sequence, the rst
element in the second sequence and the incremental value of the second sequence, respectively.

输出

For each test case, print a single line which contains a single integer representing the length of the longest
common subsequence between the given two sequences.

样例输入

3
5 3 4 15 3 1
10 2 2 7 3 3
100 1 1 100 1 2

样例输出

4
3
50

来源

 

[提交][状态]