等差数列个数-- DP

系统管理员 2020-11-14 08:55 646阅读 0赞

## Description ##

等差数列的定义是一个数列S，它满足了(S\[i\]-S\[i-1\])  =  d  (i> 1)。显然的一个单独的数字或者两个数字也可以形成一个等差数列。 经过一定的学习小C发现这个问题太简单了，等差数列的和不就是(Sn+S1)\*n/2？因为这个问题实在是太简单了，小C不屑于去解决它。这让小C的老师愤怒了，他就找了另外一个问题来问他。 小C的老师给了他一个长度为N的数字序列，每个位置有一个整数，他需要小C帮他找到这个数字序列里面有多少个等差数列。 …… 这个问题似乎太难了，小C需要你的程序帮他来解决这个问题。

## Input ##

第一行一个整数N，表示老师给出的数字序列的长度。 第二行有N个整数A\[i\]，表示数字序列每个数字的大小。（ N <= 1000 ）

## Output ##

输出只有一行一个整数，表示这个序列中的等差数列的个数（mod  9901）。

## Sample Input ##

5 1 4 2 3 7

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #include<vector>
    #include<string>
    #include<math.h>
    #include<map>
    #include<set>
    #include<algorithm>
    using namespace std;
    #define MOD 9901
    int dt[1010];
    int dp[1010][2010];
    
    int main( )
    {
      int N;
      while( scanf("%d",&N) != EOF )
      {
         for( int i = 1; i <= N; i++)
            scanf("%d",&dt[i]);
         memset(dp, 0, sizeof(dp));
         long long sum  = 0;
         for( int i = 1; i <= N; i++)
         { 
            for( int j = i - 1; j >= 1; j--)
            {
                int d = dt[i] - dt[j] + 1000;
                dp[i][d] = (dp[i][d] + dp[j][d] + 1) % MOD;
            }       
                
         }   
         for( int i = 1; i <= N; i++)
            for( int j = 0; j <= 2000; j++)
                sum += dp[i][j];     
         printf("%I64d\n",(sum + N) % MOD );
      }
      return 0;
    }