n≤100,v≤2000
从这里开始就需要DP了。
我们观察到值域很小，这提示我们把和值域相关的量记入状态表示。
用f(i,j)f(i,j)f(i,j)表示以位置i结尾，公差为j的等差数列有多少个。转移的时候，枚举一个小于i的k，满足hk=hi−jh_k = h_i - jhk=hi−j，然后从f(k,j)f(k,j)f(k,j)转移到f(i,j)f(i,j)f(i,j)。
注意，公差可以是负数，因此这里的j也可以是负数。
转移的时候要小心，不要重复或者遗漏某些情况。
复杂度O(n2k)O(n^2k)O(n2k)。
by 良辰、 @ 2019-02-12 17:23:43
思路十分明确（from:__stdcall)
by 良辰、 @ 2019-02-12 17:24:17
同求
by jor蛋 @ 2022-07-02 18:34:00
应该不是这样的60分吧？
```c
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,H=4e4+20,MOD=998244353,C=2e4+10;
using ll = long long;
int f[N][H],a[N];
int n;
ll res;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int j=-2000;j<=2000;j++){
for(int i=1;i<=n;i++){
for(int k=1;k<i;k++){
if(a[i]-a[k]==j){
f[i][j+C]=(f[k][j+C]+f[i][j+C]+1)%MOD;
res=(res+f[k][j+C]+1)%MOD;
}
}
}
}
cout<<res+n;
}
```
by jor蛋 @ 2022-07-02 19:46:21
这样？
```cpp
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
typedef long long ll;
int n;
ll h[1005], dp[1005][40005], vmx = -0x3f3f3f3f, vmn = 0x3f3f3f3f;
const ll M = 998244353LL;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld", h + i);
vmx = max(vmx, h[i]);
vmn = min(vmn, h[i]);
}
ll ans = n * 1LL;
int df = vmx - vmn;
for(int i = 1; i <= n; i++)
for(ll j = vmn - vmx; j <= df; j++) {
dp[i][j + df] = 1LL;
for(int k = 1; k < i; k++) {
if(h[k] == h[i] + j)
dp[i][j + df] = (dp[i][j + df] % M + dp[k][j + df] % M) % M;
}
}
for(int i = 1; i <= n; i++)
for(ll j = vmn - vmx; j <= df; j++)
ans = (ans % M + dp[i][j + df] % M - 1) % M;
printf("%lld", ans);
system("pause");
return 0;
}
```
by __Remake__ @ 2022-08-29 03:13:36