【51nod 1055 & 1056】最长等差数列及V2 题解

V1

题目大意

  $n$ 个不同的正整数，找出由这些数组成的最长的等差数列。
  $n \le 10000,\ a_i \le 10^9$

【$O(n^3)$】

  设 $f_{i,j}$ 表示：以第 $i$ 项和第 $j$ 项（$i>j$）作为数列最后两项，的最长长度。

  转移就是找一个 $k$，使得 $a_i-a_j=a_j-a_k$，然后就 $f_{i,j}=f_{j,k}+1$。

  三个变量的枚举，所以是 $O(n^3)$。

【$O(n^2 \log n)$】

  我们观察，枚举了 $i$ 和 $j$ 之后，$a_k$ 的值是确定的。
  那么搞个东西存下对于每个 $j$ 同一类的 $k$ 的最大 $f$ 值就好了。
  如果一开始离散化这个数组，那可以二分求这个 $k$，所以带个 $\log$。

【$O(n^2)$】

  实际上不需要离散化也不需要二分，因为如果 $j$ 从大到小枚举，那么 $k$ 是单调递减的。
  于是就 $O(n^2)$ 了。

V2

题目大意

  $n$ 个不同的正整数，问是否存在由这些数组成的等差数列长度 $\ge 200$。若没有，输出无解，若有，输出最长长度
  $n \le 50000,\ a_i \le 10^9$

【随机大法】

  我同桌说，看到 $\ge 200$ 这种东西，应当要考虑近似算法。

  随机两个下标作为数列的中间两项，然后往两边扩展。做一次的时间是 $O(n)$。
  然后不能随机太多，也不要随机重复，所以把数组打乱顺序，取前面大概1000组就可以了。

  如果要求的长度过小（比如 3），那这个算法是很难找出来的，但 200 的话还是可以的。