个不同的正整数,找出由这些数组成的最长的等差数列。
Constraints
$ n \leq 10000$
Solution
表示等差数列最后的两个数字的位置。
转移的时候考虑先固定 的位置,然后分别向两边扫寻找满足 的数对 ,并用 来更新 。
考虑到空间问题,需要使用 short int 。时间复杂度 。
Code
1 |
|
Living is do or die.
N 个不同的正整数,找出由这些数组成的最长的等差数列。
$ n \leq 10000$
dp(i,j) 表示等差数列最后的两个数字的位置。
转移的时候考虑先固定 j 的位置,然后分别向两边扫寻找满足 ai+ak=2⋅aj 的数对 (i,k) ,并用 dp(i,j)+1 来更新 dp(j,k) 。
考虑到空间问题,需要使用 short int 。时间复杂度 O(n2) 。
1 | #include<cstdio> |