小米oj 有多少个等差数列（动态规划）

有多少个等差数列？

序号：#20难度：困难时间限制：500ms内存限制：10M

描述

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

思路：设dp[i][k]表示以a[i]为起点，k为公差的等差数列的个数。

转移方程为：if(a[j]+k==a[i])dp[j][k]+=(dp[i][k]+1); (j<i)



#include<bits/stdc++.h>

#include<stdio.h>

#include<iostream>

#include<cmath>

#include<math.h>

#include<queue>

#include<set>

#include<map>

#include<iomanip>

#include<algorithm>

#include<stack>

using namespace std;

#define inf 0x3f3f3f3f

typedef long long ll;

char buf[100000];

int a[205];

ll dp[205][405];

int main()

{

#ifndef ONLINE_JUDGE

    //freopen("in.txt","r",stdin);

#endif // ONLINE_JUDGE

	while(gets(buf))

    {

    memset(dp,0,sizeof(dp));

    int v;

    int n=0;

    char *p=strtok(buf," ");

    while(p)

    {

        sscanf(p,"%d",&v);

        a[n++]=v;

        p=strtok(NULL," ");

    }

    ll ans=0;

    for(int k=-200;k<=200;k++)

    {

        for(int i=n-1;i>=0;i--)

        {

            for(int j=i-1;j>=0;j--)

            {

                if(a[j]+k==a[i])

                    dp[j][k+200]+=(dp[i][k+200]+1);

            }

        }

    }

    for(int i=0;i<n;i++)

    {

        for(int k=0;k<=400;k++)

        {

            ans+=dp[i][k];

        }

    }

    cout<<ans<<endl;

    }

    return 0;

}

巴特西

小米oj 有多少个等差数列（动态规划）

最新文章

热门文章