Arithmetic Progressions
鏈接：https://ac.nowcoder.com/acm/contest/7831/B
來源：牛客網

題目描述

An arithmetic progression is a sequence of numbers a1, a2, ..., ak where the di?erence 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 di?erence 3. In this problem, you are requested to ?nd 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 di?erence 3, or 9, 5, 1 with the common di?erence ?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; }

總結

以上是生活随笔為你收集整理的2020牛客国庆集训派对day4 Arithmetic Progressions的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。