Arithmetic Progressions
贴个链接
题意
给一个数字的集合，让从集合中选出一些数让他们构成等差数列，问做多能选的数有多少个 集合大小：5000
题解
这题都不会？我是好菜了，，我好菜，自闭ing dp[i][j] 表示第 i 个数字是倒数第二项，第 j 个数字是最后一项的最长长度。 所以转移怎么转移？ 肯定是枚举 i 、j 然后枚举i之前的一个位置pos，从dp[pos][i] 转移过来。 pos 得满足：a[j] - a[i] == a[i] - a[pos]; 并且pos 得是 i 前面离 i 最近的那个位置。
dp
[i
][j
] = dp
[pos
][i
] + 1;
但是这就n的三次了。于是发现枚举 j 的时候满足条件的pos 是递减的。 所以可以枚举的时候用一个指针跟着跑， 并不是二分。。。 二分还得有个logn 5000 * 5000 * log(5000) 不知道会不会tle 。。 所以就变为了n ^ 2.
垃圾代码：
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <stack>
#include <map>
#include <bitset>
#include <math.h>
#include <set>
#include <unordered_set>
#include <climits>
using namespace std
;
typedef long long ll
;
typedef pair
<int,ll
> pii
;
typedef pair
<ll
,ll
> pll
;
typedef pair
<double,double> pdd
;
typedef unsigned long long ull
;
typedef unordered_set
<int>::iterator sit
;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void tempwj(){freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll
gcd(ll a
,ll b
){return b
== 0 ? a
: gcd(b
,a
% b
);}
ll
qpow(ll a
,ll b
,ll mod
){a
%= mod
;ll ans
= 1;while(b
> 0){if(b
& 1)ans
= ans
* a
% mod
;a
= a
* a
% mod
;b
>>= 1;}return ans
;}
struct cmp
{bool operator()(const pii
& a
, const pii
& b
){return a
.second
> b
.second
;}};
int lb(int x
){return x
& -x
;}
const int inf
= INT_MAX
;
const ll INF
= 0x3f3f3f3f3f3f3f;
const ll mod
= 1e9+7;
const int maxn
= 1e5 + 10;
const int M
= 100005;
int a
[maxn
];
int dp
[5005][5005];
int main()
{
int n
;
scanf("%d",&n
);
for (int i
=1; i
<= n
; i
++ )
scanf("%d",&a
[i
]);
sort(a
+ 1, a
+ 1 + n
);
int ans
= 0;
for (int i
=1 ;i
<= n
; i
++ )
{
int pos
= i
- 1;
for(int j
= i
; j
<= n
; j
++ )
{
dp
[i
][j
] = 2;
while(pos
> 0 && a
[j
] - a
[i
] > a
[i
] - a
[pos
])
pos
-- ;
if(pos
> 0 && a
[j
] - a
[i
] == a
[i
] - a
[pos
])
dp
[i
][j
] = dp
[pos
][i
] + 1;
ans
= max(ans
,dp
[i
][j
]);
}
}
printf("%d\n",ans
);
}
