【codevs2205】等差数列

题目大意：给定一个长度为 N 的序列，求这个序列中等差数列的个数。

题解：根据题意应该是一道序列计数 dp。设 (dp[i][j]) 表示以第 i 项结尾，公差为 j 的等差数列的个数，则状态转移方程为 (dp[i][d]=sumlimits_{j=1}^{i-1} dp[j][d])。由于一个单独的数字也是一个等差数列，因此需要将答案加 N。同时，答案的贡献需要在状态转移的时候计算，因为这里第二层枚举的并不是公差，而是元素下标，且最后进行计算也比较困难。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
const int mod=9901;

int n,ans,a[maxn],dp[maxn][maxn<<1];

void read_and_parse(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	ans=n;
}

void solve(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++){
			int d=a[j]-a[i]+1000;//偏移量：公差最大是1000
			dp[i][d]+=dp[j][d]+1;
			ans=(ans+dp[j][d]+1)%mod;
		}
	printf("%d
",ans);
}

int main(){
	read_and_parse();
	solve();
	return 0;
}