P1091 （C++代码）

解题思路:





注意事项:





参考代码:

#include <stdio.h>  
#include <string.h>  
  
long long dp[1002][2002];  
  
int num[1002];  
int main()  
{  
    int n;  
    scanf("%d", &n);  
  
    memset(dp, 0, sizeof(dp));  //初值为0   
    for (int i=1; i<=n; ++i)  
    {  
        scanf("%d", &num[i]);  
    }  
    int cha;  
  
    for (int i=2; i<=n; ++i)  
    {  
        for (int j=1; j<=i-1; ++j)  
        {  
            cha = num[i]-num[j] + 1000; // 当前和前面某个差值  
            dp[i][cha] += dp[j][cha]+1; // 前面j个组成的数列,添加num[i],组成新的数列,所以要+1  
        }  
    }  
    long long sum = n; // 每一个数都是等差数列  
    for (int j=1; j<=n; ++j)  
    for (int i=0; i<=2000; ++i)  
    {  
        sum += dp[j][i];  
        sum %= 9901;  
    }  
    printf("%lld\n", sum);  
    return 0;  
}