Two Melodies
题意翻译
给定一个$n$,以及$n$个数
$a_1,a_2,a_3,\cdots,a_n$,定义一个$Melody$子序列(和"最长上升子序列"中的"子序列"定义一样,是指在原序列中相对顺序不变但是不一定连续的一段子序列)如下:
对于任意相邻的两个元素,一定满足这两个元素差为1或者两个元素除7同余。
请在原序列中找出两个无重复部分的Melody子序列并且选出的两个长度加起来最大。
> 解释:样例2中选出$62,48,49$和$60,61$这两个Melody子序列能使得总长度最大$=5(\text{即2+3})$。
题目描述
Alice is a beginner composer and now she is ready to create another masterpiece. And not even the single one but two at the same time!
Alice has a sheet with $ n $ notes written on it. She wants to take two such non-empty non-intersecting subsequences that both of them form a melody and sum of their lengths is maximal.
Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
Subsequence forms a melody when each two adjacent notes either differs by 1 or are congruent modulo 7.
You should write a program which will calculate maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.
输入输出格式
输入格式
The first line contains one integer number $ n $ ( $ 2<=n<=5000 $ ).
The second line contains $ n $ integer numbers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{5} $ ) — notes written on a sheet.
输出格式
Print maximum sum of lengths of such two non-empty non-intersecting subsequences that both of them form a melody.
输入输出样例
输入样例 #1
4
1 2 4 5
输出样例 #1
4
输入样例 #2
6
62 22 60 61 48 49
输出样例 #2
5
说明
In the first example subsequences $ [1,2] $ and $ [4,5] $ give length 4 in total.
In the second example subsequences $ [62,48,49] $ and $ [60,61] $ give length 5 in total. If you choose subsequence $ [62,61] $ in the first place then the second melody will have maximum length 2, that gives the result of 4, which is not maximal.