Codeforces Gym 102082B – Arithmetic Progressions

题目链接:Gym – 102082B

$dp(i,j)$代表以$a_j,a_i$结尾的等差数列的最长长度。那么,我们需要$O(n^2)$地枚举出$2 \leq j < i \leq n$,对于每次枚举出的$a_j$和$a_i$,寻找出前一项$p = 2 \times a_j – a_i$。注意,要先对$\{ a_n \}$序列排序,由于保证每个数都是不一样的,那么$p$如果存在,有且只有一个,可以在排好序的序列中二分找到。这个时候$dp(i,j) = \max \{ dp(i, j), dp(j,p) \}$。

初始化所有的$dp(i,j) = 2, 1 \leq j < i \leq n$。

 

3
说点什么

avatar
50
2 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
YuweiZhao0xfanerDDDD Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
DDDD
游客
DDDD

发现一枚大佬。orz

0xfaner
游客
0xfaner

tql