1055最长等差数列

关键词：

第1行：N，N为正整数的数量(3 <= N <= 10000)。
第2 - N+1行：N个正整数。(2<= A[i] <= 10^9)

最长等差数列的长度。

10
1
3
5
6
8
9
10
12
13
14

5

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<iostream>
 4 #include<queue>
 5 #include<math.h>
 6 #include<string.h>
 7 #include<algorithm>
 8 using namespace std;
 9 typedef long long LL;
10 short int dp[10005][10005];
11 LL ans[10005];
12 using namespace std;
13 int main(void)
14 {
15     int i,j;
16     for(i = 0; i <= 10000; i++)
17     {
18         fill(dp[i],dp[i]+10001,2);
19     }
20     int n;
21     scanf("%d",&n);
22     for(i = 1; i <= n; i++)
23     {
24         scanf("%lld",&ans[i]);
25     }
26     sort(ans+1,ans+n+1);
27     int l ,r;short int an = 2;//printf("%d
",n);
28     for(i = n-1; i >= 1 ; i--)
29     {
30        l = i-1;r = i+1;
31        while(l >= 1&&r <= n)
32        {
33            if(ans[l] + ans[r] ==(LL)2*ans[i])
34            {
35                dp[l][i] = dp[i][r] + 1;
36                an = max(an,dp[l][i]);
37                l--;
38            }
39            else if(ans[l] + ans[r] < (LL)2*ans[i])
40            {
41                r++;
42            }
43            else l--;
44            //printf("%d
",dp[l][i]);
45        }
46     }
47     printf("%d
",an);
48     return 0;
49 }

51nod1055最长等差数列

... 80 N个不同的正整数，找出由这些数组成的最长的等差数列。  例如：13568910121314等差子数列包括(仅包括两项的不列举）13515913369123813591368101214 其中68101214最长，长度为5。  Input 查看详情

51nod1055最长等差数列

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1055题意： 思路：先固定一个位置，然后从该中心点出发向两边扫，确实很难想到啊。。。1#include<iostream>2#include<algorithm>3#include<cstring>4#include<cs 查看详情

51nod1055最长等差数列

完全一脸懵逼！。dp[i][j]表示i,j为相邻的两项的最大值。两个指针两边扫的思想好劲啊这个！%%%#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>usingnamespacestd;#definerep(i,s,t)for(inti=s;i<=t;i++ 查看详情

51nod1055最长等差数列(代码片段)

...题，用f[i][j]表示以i为最后一个数、以j为倒数第二个数的等差数列的长度。转移显然，不过在寻找满足a[i]-a[j]=a[j]-a[k]的k的时候，要注意随着i的递增，k其实是递减的，所以总的复杂度可以降到n^2.　　1#include<cstdio>2#include<a... 查看详情

thelongestsubsequencewithequalstep最长等差序列/最长等差数列(代码片段)

DescriptionGivenanarrayofintegers X andaninteger step,findthelengthofthelongestsubsequenceof X whereintegersinthissubsequenceformanarithmeticsequencewithdifferenceof step.SampleInputThestringformofana 查看详情

51nod1056最长等差数列v2

1056 最长等差数列 V2基准时间限制：8 秒空间限制：131072 KBN个不同的正整数，从中选出一些数组成等差数列。  例如：13568910121314等差子数列包括(仅包括两项的不列举）13515913369123813591368101214 其中68101214... 查看详情

thelongestsubsequencewithequalstep最长等差序列/最长等差数列(代码片段)

DescriptionGivenanarrayofintegers X andaninteger step,findthelengthofthelongestsubsequenceof X whereintegersinthissubsequenceformanarithmeticsequencewithdifferenceof step.SampleInputThestringformofanarrayisinthefirstline.Thesecondlindisaninteger(stringform).2417-2-3-5-3SampleOutputAninteger.4E... 查看详情

51nod1056最长等差数列v2

...分值: 1280 N个不同的正整数，从中选出一些数组成等差数列。  例如：13568910121314等差子数列包括(仅包括两项的不列举）13515913369123813591368101214 其中68101214最长，长度为5。 现在给出N个数，你来从中 查看详情

蓝桥杯最长等差素数数列

[题目]　　在小于10的素数中有3、5、7组成的等差数列，在小于30的素数中有11、17、23、29组成的等差数列。　　试找出区间[100,1000]内的素数构成的最大等差数列（即等差数列包含的素数个数最多）并打印输出。[关键字]　　素数... 查看详情

leetcode.1027最长等差数列(代码片段)

题目链接Leetcode.1027最长等差数列Rating：1759题目描述给你一个整数数组nums，返回nums中最长等差子序列的长度。回想一下，nums的子序列是一个列表nums[i1],nums[i2],...,nums[ik]，且0<=i1<i2<...<ik<=nums.length-1... 查看详情

leetcode打卡——等差数列题目(lis变式)——1218.最长定差子序列(代码片段)

...IS的不同点：LIS是最长递增子序列，而此题是给出等差数列的公差后，求出最长等差子序列，不同之处在哪 查看详情

牛牛的数列最长递增子序列

....nowcoder.com/questionTerminal/4e1012fe691b446d88eba5db8f511692要求一个最长连续子序列，这个序列中只更改一个数字，便是最长连续递增子序列。设更改的数字位于A[i]，对A[i]，计算出以A[i-1]为结尾的最长递增子序列，以A[i+1]为开始的最长子... 查看详情

thelongestcommonconsecutivesubsequenceofxandy最长公共连续子数列/最长公共连续子序列(代码片段)

DescriptionGiven2arrays X and Y,returntheMAXIMUMlengthofthelongestcommonconsecutivesubsequence.Ifnosuchsubsequenceexists,return0.Aconsecutivesubsequenceof X isasliceof X,whichmeans X[i:j], 0≤i<j≤le 查看详情

nefu1118最长上升子序列(lis)

discription：定义臻.排序数列如下：一个数列删去其中一个数后是从小到大排好序的，称这个数列为臻.排序数列。现在给你一个数列，判断它是否为臻.排序数列。intput：多组输入数据，每组有两行，第一行一个整数n(2<=n<=10000... 查看详情

hdu1069(最长单调递减数列)

...。注意长方体是能够调整的。就是依照长和宽来排序，找最长的单调递减的数列。我们用dp[i]来表示搭建到第i块长方体的时候塔的最高高度，那么状态转移方程就是dp[i]=max(dp[i],dp[j]+s[i].h)。 查看详情

scu-4441necklace（树状数组求最长上升子数列）

Necklacefroghas (n) gemsarrangedinacycle,whose beautifulness are (a_1,a_2,dots,a_n).Shewouldliketoremovesomegemstomakethemintoa beautifulnecklace withoutchangin 查看详情

dp的练习题；

...不会，于是开了这篇随笔来巩固（重学）一下dp；B-最长等差数列N个不同的正整数，找出由这些数组成的最长的等差数列。  例如：13568910121314等差子数列包括(仅包括两项的不列举）13515913369123813591368101214 其中68101214最... 查看详情

codevs1006等差数列

...lt;=100)个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度.输入描述 InputDescription第一行是一个整数n,接下来一行包括了n个数,每个数的绝对值不超过10000000.输出描述 OutputDescription对于每个... 查看详情