[Usaco2004]等差数列
题目大意：约翰发现奶牛经常排成等差数列的号码．他看到五头牛排成这样的序号：“1，4，3，5，7”很容易看出“1，3，5，7”是等差数列。给出N(1≤N≤2000)数字AI..AN(O≤Ai≤10^9)，找出最长的等差数列，输出长度．
数据范围：如题面。
题解：
以为是啥神仙题，结果看见了$1\le N\le 2000$。
可以$N^2$啊.......
考虑$DP$呗，设$f_{(i, j)}$表示第$A_i$个数为等差数列第一项，$A_j$为等差数列第二项的最长等差序列。
显然，我们就需要找到$A_j$后面，离$A_j$最近的等于$2*A_j-A_i$的位置$k$，用$f_{(j, k)} +1$更新$f_{(i, j)}$即可。
这个咋找呢？
我是弄了个$map$，复杂度变成$O(N^2logN)$。
代码：
#include <bits/stdc++.h>
#define N 2010
using namespace std;
int a[N], f[N][N];
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == '-')
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}
map<int, int>MP;
int main() {
int n = rd();
if (n == 1)
puts("1"), exit(0);
for (int i = 1; i <= n; i ++ ) {
a[i] = rd();
}
MP[a[n]] = n;
for (int i = 1; i < n; i ++ ) {
f[i][n] = 2;
}
for (int j = n - 1; j >= 2; j -- ) {
for (int i = 1; i < j ; i ++ ) {
f[i][j] = 2;
int to = a[j] + a[j] - a[i];
// int id = MP.count(to);
// printf("%d %d %d %d %d %d\n", i, j, a[i], a[j], to, id);
if (MP.count(to)) {
f[i][j] = max(f[i][j], f[j][MP[to]] + 1);
}
}
MP[a[j]] = j;
}
int ans = 0;
for (int i = 1; i <= n - 1; i ++ ) {
for (int j = i + 1; j <= n; j ++ ) {
// printf("%d %d %d\n", i, j, f[i][j]);
ans = max(ans, f[i][j]);
}
}
cout << ans << endl ;
return 0;
}
小结：做题看数据范围是很重要的，还有$map$在判断有没有值的时候要用$.count()$，不然会新建点。而且这东西是个$bool$，并不是$[]$的进化版。