【codevs2205】等差数列

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

题解：根据题意应该是一道序列计数 dp。设 \(dp[i][j]\) 表示以第 i 项结尾，公差为 j 的等差数列的个数，则状态转移方程为 \(dp[i][d]=\sum\limits_{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\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【codevs2205】等差数列

最新文章

热门文章