MIOJ #20 有多少个等差数列?

描述

等差数列是常见数列的一种,如果一个数列从第二项起,每一项与它的前一项的差等于同一个常数,这个数列就叫做等差数列,而这个常数叫做等差数列的公差,公差常用字母d表示。即对于数列S,它满足了(S[i]-S[i-1]) = d (i \gt 1)(S[i]S[i1])=d(i>1)。 显然,一个数字无法构成等差数列,而任意两个数字可以形成一个等差数列。 这里给出了一个长度为N(0<N<200)的数字序列,每个位置有一个整数(100整数100),需要找到这个数字序列里包含多少个等差数列,序列顺序固定,无需排序。 输入数据格式:{S[0] S[1] S[2] … S[N]}S[0] S[1] S[2] … S[N](以半角空格符分隔,N>1) 输出数据格式:等差数列数量 MM; 其中数列 SS 的项为整数

请注意时间复杂度的限制。

输入

输入一个数列[ 2 7 4 5 6 ],该数列包含等差数列: [ 2 7 ] [ 2 4 ] [ 2 5 ] [ 2 6 ] [ 7 4 ] [ 7 5 ] [ 7 6 ] [ 4 5 ] [ 4 6 ] [ 5 6 ] [ 2 4 6 ] [ 4 5 6 ]

输出

上例共包含12组等差数列,故应输出12

输入样例

2 7 4 5 6
3 3 3 3

输出样例

12
11

AC代码:

#include <bits/stdc++.h>
#include<iostream>
#include<map>
using namespace std;

int dp[400+1][400+1];

int main()
{
        memset(dp,0,sizeof(dp));
        int b;
        int result = 0;
        vector<int>a;
        bool flag = false;
        while(cin>>b)
        {
            a.push_back(b);
            if (cin.get() == '\n')
                break;
        }
        for(int k = -200; k<=200; k++)
        {
            for(int j = 0; j<a.size(); j++)
            {
                for(int i = j+1; i<a.size(); i++)
                {
                    if(a[j]+k == a[i])
                    {
                        dp[i][k+200] = dp[i][k+200] + dp[j][k+200]+1;
                    }//k+200 因为数组下标必须大于等于0
                }
            }
        }
        for(int i = 0; i<a.size(); i++)
        {
            for(int k = -200; k<=200; k++)
            {
                result = result + dp[i][k+200];
            }
        }
        cout<<result<<endl;
}

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注