LEM5 - ARITHMETIC PROGRESSION
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
//#include <conio.h>
//double const PI=4*atan(1);
using namespace std;
struct so{
int gt,tt;
};
bool cmp1(so A1,so A2){
return A1.gt<A2.gt;
}
bool cmp2(so A1,so A2){
return A1.tt<A2.tt;
}
int n,f[100011][102],g[10111111],tong,kq;
so A[111111];
int main(){
// freopen("LEM5.in","r",stdin);
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d",&A[i].gt);
A[i].tt = i;
}
sort(A+1,A+n+1,cmp1);
tong = A[1].gt; A[1].gt = 0;
// for(int i = 1;i<=n;i++) printf("%d ",A[i].gt);
for(int i = 1;i<n;i++){
if(A[i+1].gt-tong-A[i].gt>100)
tong+=A[i+1].gt-tong-A[i].gt-101;
A[i+1].gt-= tong;
}
sort(A+1,A+n+1,cmp2);
// for(int i = 1;i<=n;i++) printf("%d ",A[i].gt);
memset(g,0,sizeof(g));
kq = 0;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=100;j++){
if(A[i].gt-j>=0 &&g[A[i].gt-j]>0)
f[i][j] = f[g[A[i].gt-j]][j]+1;
else f[i][j] = 1;
kq = max(kq,f[i][j]);
// printf("%d\n",kq);
}
g[A[i].gt] = i;
}
printf("%d",kq);
// getch();
}