Arithmetic Progressions 链接：https://ac.nowcoder.com/acm/contest/7831/B 来源：牛客网
题目描述
An arithmetic progression is a sequence of numbers a1
, a2
, ..., ak where the difference of consecutive members ai
+1−ai is a constant
(1 ≤ i ≤ k−
1). For example
, the sequence
5, 8, 11, 14, 17 is an arithmetic progression of length
5 with the common difference
3.
In
this problem
, you are requested to find the longest arithmetic progression which can be formed selecting some numbers from a given set of numbers
. For example
, if the given set of numbers is
{0, 1, 3, 5, 6, 9}, you can form arithmetic progressions such as
0, 3, 6, 9 with the common difference
3, or 9, 5, 1 with the common difference −
4. In
this case, the progressions
0, 3, 6, 9 and 9, 6, 3, 0 are the longest
.
输入描述: 示例1 输入 复制
6
0 1 3 5 6 9
输出 复制
4
示例2 输入 复制
7
1 4 7 3 2 6 5
输出 复制
7
示例3 输入 复制
5
1 2 4 8 16
输出 复制
2
题意：
给定一些数，允许重新排列，求其中最长的等差数列的长度
题解：
队友做得。。。队友说是简单dp p[i][j] 表示区间[i, j] 的最大等差序列长度，从当前位置往前往后找满足条件的区间，如果有就加一，边界dp[i][i + 1] = 2，不难理解，其实任意dp[i][j]（j！=i） 最小都为2.
代码：
#include<bits/stdc++.h>
#define maxn 6000
using namespace std
;
int dp
[maxn
][maxn
];
long long a
[maxn
];
int n
;
int main(){
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++){
scanf("%lld",&a
[i
]);
}
sort(a
+1,a
+1+n
);
int ans
=0;
for(int i
=1;i
<=n
;i
++){
int k
=i
-1;
for(int j
=i
+1;j
<=n
;j
++){
dp
[i
][j
]=2;
int d
=a
[j
]-a
[i
];
while(k
>=1&&a
[i
]-a
[k
]<d
){
k
--;
}
if(k
==0||a
[i
]-a
[k
]!=d
)
continue;
dp
[i
][j
]=max(dp
[i
][j
],dp
[k
][i
]+1);
ans
=max(ans
,dp
[i
][j
]);
}
}
printf("%d",ans
==0? 2 : ans
);
return 0;
}
