3239. 最长的等差数列

Saitama

eoj跑的真他娘的快啊

10175102262 LarsPendragon

被暴力标签骗了……直接动手写,后来才发现有问题……然后大改……
虽然说也是暴力没错……
给几组数据自行体会:一、10 1 1 2 2 3 3 4 4 5 5(答案5); 二、7 1 2 4 5 6 8 9(答案4)
附C代码:

#include <stdio.h>
#include <stdlib.h>
int cmp(const void*a, const void*b)
{
    int *p1=(int*)a, *p2=(int*)b;
    return *p1-*p2;
}
int main()
{
    int T, I;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        int n, i, j, k, cnt, max=1, x, y, num[100];
        scanf("%d",&n);
        for(i=0; i<n; i++) scanf("%d",&num[i]);
        qsort(num, n, sizeof(int), cmp);
        if(n==2) max=2;
        else if(n>2)
        {
            for(i=0; i<n-2; i++)
            {
                for(j=i+1; j<n-1; j++)
                {
                    cnt=2;
                    x=num[j]-num[i];
                    y=num[j];
                    for(k=j+1; k<n; k++) if(!(num[k]-y-x)) {y=num[k]; cnt++;}
                    if(cnt>max) max=cnt;
                }
            }
        }
        printf("case #%d:\n%d\n",I,max);
    }
    return 0;
}
Gottfried_Leibniz

此题能够使用枚举法完全是因为数据量过小
O(n^3)的算法在更大的数据量下是完全行不通的
dfs才是此类题目的精髓所在,感兴趣的同学可以细品一下

#include <iostream>
#include <vector>
#include <algorithm>
//#define ACM
#define For(i,m,n) for(int32_t i = m; i < n; i++)
using namespace std;
int32_t ans = 1, T = 0, n = 0;
vector<int32_t>seq;
int32_t dfs(const int32_t& k, const bool& flag, int32_t base);
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
#ifdef ACM
    freopen("最长等差数列.in","r",stdin);
#endif // ACM
    cin >> T;
    For(i,0,T){
        ans = 1;
        cout << "case #" << i << ":\n";
        cin >> n;
        seq = vector<int32_t>(n);;
        For(j,0,n){
            cin >> seq[j];
        }
        sort(seq.begin(),seq.end());
        For(k,0,n-1){
            ans = max(ans,dfs(k,0,0));
        }
        cout << ans << '\n';
    }
    return 0;
}

int32_t dfs(const int32_t& k, const bool& flag, int32_t base)
{
    int32_t len = 1;
    if(k == n - 1){
        return len;
    }
    if(flag == 0){
        int32_t plen = len;
        For(i,k+1,n){
            base = seq[i] - seq[k];
            int32_t tmp = plen + dfs(i,1,base);
            len = max(tmp,len);
        }
    }
    if(flag == 1){
        int32_t plen = len;
        For(i,k+1,n){
            if(seq[i] - seq[k] == base){
                int32_t tmp = plen + dfs(i,1,base);
                len = max(tmp,len);
            }
        }
    }
    return len;
}
Master X

每次做这种题目的时候
我就在想
又到了挑战EOJ速度的时候了…………
不要想任何骚代码,直接暴力!

1.我们第一个枚举的是起始点i
2.枚举差点j,即我们当前选择的差为a[j]-a[i](i+1≤j≤n)
3.枚举剩余部分k,我们在遍历时便可以查询是否是等差序列,如果差>我们选择的差,就可以Break
4.求过程中最大长度
时间复杂度O(nlogn+n^3)

你当前正在回复 博客/题目
存在问题!