撰写
题意：找出整数序列中最长的等差数列。
题解：
- 一开始直接用了map加上简单哈希，但是Memory limit，可以试着手动写散列表来实现,时间复杂度O(n^2).
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include
<map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
template <class T>
inline bool scan_d(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='?'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='?')?-1:1;
ret=(c=='?')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10);
putchar(x%10+'0');
}
const ll base=1e9;
const int MAXN = 5e3+10;
map<ll,int>mp;
map<ll,int>ccnt;
int a[MAXN];
int b[MAXN];
int main() {
int n;
scanf("%d", &n);
rep(i,1,n) {
scan_d(b[i]);
}
int cnt=1;
sort(b+1,b+n+1);
int ans=0;
int f=0;
a[1]=b[1];
rep(i,2,n) {
if(b[i]==b[i-1]) {
f++;
continue;
} else {
if(f>ans)ans=f;
f=0;
}
a[++cnt]=b[i];
}
n=cnt;
rep(i,1,n) {
rep(j,1,i-1) {
ll d=a[i]-a[j];
mp[d*base+a[i]]+=mp[d*base+a[j]]+1;
map<ll,int>::iterator it=mp.find(mp[d*base+a[j]]);
if(it!=mp.end()) mp.erase(it);
if(ans<mp[d*base+a[i]])ans=mp[d*base+a[i]];
}
}
printf("%d", ans+1);
return 0;
}
- 可以用dp解决，时间复杂度大于O(n^2)。（最坏n^3）
- 将dp[i][j]看作以a[i]，a[j]为结尾的等差数列；（或者开头也行，只要改变i，j的顺序即可）
- if(a[j]-a[i]==a[i]-a[pre])d[i][j]=max(dp[i][j],dp[pre][i]);
- 不可以用滚动数组节省空间，因为并没有一种dp顺序能够覆盖原来的状态或将上一轮的最大值当作本轮的状态比较。
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include
<map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
template <class T>
inline bool scan_d(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='?'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='?')?-1:1;
ret=(c=='?')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10);
putchar(x%10+'0');
}
const int MAXN = 1e5+10;
int n;
int a[MAXN];
int dp[5005][5005];
int main()
{
// ios::sync_with_stdio(0);
// ifstream in;
// ofstream out;
// in.open("test.txt");
// out.open("output.txt");
scan_d(n);
rep(i,1,n) scan_d(a[i]);
sort(a+1, a+n+1);
rep(i,1,n)
rep(j,1,n)
dp[i][j] = 2;
int ans = 2;
rep(i,1,n-1){
int pre = i - 1;
rep(j,i+1,n){
while (pre>0&&a[j]-a[i]>a[i]-a[pre])pre--;//向前找，因为有中间的于i不连续但满足条件的pre存在（正如i，j可以不连续）
if (pre > 0 && a[j]-a[i]==a[i]-a[pre])//就是判断第一个小于等于的符不符合公差d咯
dp[i][j] = dp[pre][i] + 1;
ans = max(ans, dp[i][j]);
}
}
cout << ans << endl;
return 0;
}
- 可以用二分解决：时间复杂度大于O(n^2logn)（最坏N^3logn）
- 枚举以a[i],a[j]开头的所有等差序列
- 用二分查找下一个元素是否存在
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
// freopen("in.txt","r",stdin);
int n;
int a[5010];
while(cin>>n)
{
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int d;
int num;
int kase=2;
int ans=2;
for(int i=0;i<n-ans;i++)
/*这里遍历到n-ans就够了,因为当你的结果是ans是，在从n-ans往后找，即便后面都是等差序列，答案也不会超过ans*/
for(int j=i+1;j<n-ans;j++)
{
d=a[j]-a[i];
num=a[j];
kase=2;//更新kase
while(1)
{
num=num+d;
if(binary_search(a,a+n,num))
kase++;
else
{
ans=max(ans,kase);
break;
}
}
}
cout<<ans<<endl;
}
return 0;
}