304264: CF813D. Two Melodies
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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