[ABC362E]Count Arithmetic Subsequences

题目大意

给定\(N\)个数字的序列，每个元素为\(a[i]\)，问长度为i的数字序列是由多少个子序列构成的？
定义数字序列：
如果\(a[i]-a[j]==a[k]-a[i]\)，则\(a[j],a[i],a[k]\)构成数字序列

数据范围

\(N \leq 80, a_i \leq 10^9\)

题解

一看到这个数据范围，就和\(a[i]\)没关系，肯定是和\(N\) 有关系，是\(N^4或者N^3\)
要构成数字序列，是一个等差序列，肯定和等差有关，如果我们枚举等差的话，肯定会超时
这个数据范围，感觉可以区间DP，既然是区间DP，状态定义应该为
\(f[i][j][k]\)表示\(i\)和\(j\)之间构成长度为\(l\)的数字序列的子序列的个数，要求\(a[i]\)和\(a[j]\)是数字序列的头和尾
根据头尾，我们能算出来等差是多少，\(i和j\)这个区间里面并不是每个元素都要参与
如何转移呢？
\(f[i][j][l]=f[i][j][l]+f[i][k][l-1] if a[i]……a[k],a[j]是等差序列的话\)
这样的话，这个题就解决了

启示

最重要的是一定要看数据范围，决定用什么样的DP