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();
}

Download