51nod 1056 최 장 등차 수열 V2

이것 은 1055 문제 와 차이 가 많 지 않 아서 조금 만 고치 면 지나 간다. 먼저 가 지 를 자 르 는 개작 이다. 이 가 지 를 자 르 는 것 은 반드시 지나 가 는 것 이다. 당 선생님 은 토론 에서 증명 하 셨 다.
우선 등차 수열 의 정 의 를 명 확 히 해 야 한다.
하나의 등차 수열 은 첫 번 째 항목, 공차 와 항 수 를 사용 할 수 있 는 3 원 그룹 이다. 
(first,delta,length) 물론 
first 마지막 으로 바 꿀 수도 있어 요. 
last ，너의 알고리즘 에 달 려 있다.
우리 가 고려 해 야 할 등차 수열 은 가능 한 한 적은 정보 로 모든 가능성 을 표시 해 야 한다. 즉, 추출 한 등차 수열 간 에 서로 포 함 된 관계 가 있어 서 는 안 된다 는 것 이다. 예 를 들 어 
(2,3,4) 화해시키다 
(2,3,5) 군더더기 
(2,3,4) 화해시키다 
(5,3,4) 같은 서열 에 나타 날 때 
(2,3,5) 존재 합 니 다.
그래서 우 리 는 만족 만 을 생각해 야 한다. 
(first−delta) 이 숫자 는 존재 하지 않 습 니 다. 그리고... 
(last+delta) 이 숫자 에 존재 하지 않 는 등차 수열.
다음은 이런 등차 수열 이 
k 충분히 컸 을 때 는 많 지 않다.
정의: 집합 에 있 는 두 요 소 는 충분히 인접 해 있 으 며, 그들의 순위 차이 만 초과 하지 않 을 때 
nk−1 。비둘기 둥지 의 원 리 를 통 해 알 수 있 듯 이 하나의 길 이 는? 
k 등차 수열 은 반드시 적어도 포함 된다. 
k−12 충분 한 인접 요소 (등차 수열 에서 순위 가 가장 작은 것 과 순위 가 가장 큰 두 요 소 를 고려).
집합 에서 충분히 인접 한 원소 의 대 수 는 초과 하지 않 는 다 
n22(k−1) ，우리 가 원 하 는 서로 다른 등차 수열 도 같은 한 쌍 의 충분 한 인접 요 소 를 포함 하지 않 기 때문에 우리 가 얻 을 수 있 는 등차 수열 의 수량 은 초과 하지 않 는 다. 
n2(k−1)2 라 고 적 었 다.
마지막 으로 이 성질 을 이용 하여 상응하는 알고리즘 을 구성 해 야 한다.
수량 이 많 지 않 은 성질 을 이용 하여 우 리 는 모든 길이 가 적어도 200 인 등차 수열 을 찾 아 그 중에서 가장 긴 것 을 선택 할 수 있다.
위의 증명 이 집합의 크기 를 이 용 했 음 을 주의 하면 유사 하 게 도 이러한 등차 수열 은 반드시 있 음 을 증명 할 수 있다 
⌊k2⌋ 앞서 가다 
⌊n2⌋ 작은 원소 집합 에 있 거나 
⌊k2⌋ 앞서 가다 
⌈n2⌉ 큰 원소 집합 에서
한편, 집합 크기 가 반 으로 줄 어드 는 동시에 수열 항 수 를 반 으로 줄 이 는 것 은 수열 수량 에 미 치 는 영향 이 크 지 않 기 때문에 집합 에 대한 분 치 를 시도 하고 더 작은 상황 의 해 를 찾 아 큰 집합 에 넣 어 왼쪽 에서 오른쪽으로 시도 할 수 있다. 
O(k) 확장 하고 다시 무 게 를 제거 하여 현재 상황 의 해 를 얻는다.
설치 해도 무방 하 다 
T(n,k) 에서 
n 추출 길이 
k 등차 수열 의 복잡 도 는 
T(n,k)=2T(n2,k2)+O(n2k2k)⇒T(n,k)=O(n2klognk)。
그 다음 에 hash 라 는 hash 는 손 으로 때 려 야 합 니 다. hash 는 바로 이전의 dp 배열 을 바 꾸 는 것 입 니 다.폭력 적 으로 찾 아 봐.마지막 으로 내 가 말 하고 싶 은 것 은 130 개의 고 개 를 끄 덕 이 는 방 패 를 써 서 1 등 을 할 수 있 을 줄 알 았 는데 2 등 을 할 줄 누가 알 았 겠 는가 하 는 것 이다.코드 는 그냥 보 냈 죠...

#include
#include
#define ll long long
using namespace std;
const int mod=233333;

int a[50010],ha[mod],ans=199,last[50010],n;
int read(){
	char c=getchar();int k=0;for (;c<48||c>57;c=getchar());
	for (;c>47&&c<58;c=getchar()) k=(k<<3)+(k<<1)+c-48;return k;
}
void add(int k,int i){
	int x=k%mod;last[i]=ha[x];ha[x]=i;
}
bool find1(int k){
	if (k>a[n]) return 0;
	for (int i=ha[k%mod];i;i=last[i])
		if (a[i]==k) return 1;
	return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+n+1);
     for(int i=1;i<=n;i++)add(a[i],i);
    for(int i=2;i<=n-ans;i++)
    {
        int j=i-1,k=i+1;
        while(j>0&&k<=n)
        {
            if(a[j]+a[k]>2*a[i])j--;
       else if(a[j]+a[k]<2*a[i])k++;
        else
       {
           ll d=a[i]-a[j];
           ll maxn=d*(ll)ans+(ll)a[j];
           if(maxn>a[n])break;
          int now=3,now1=a[k]+d;
          for(;find1(now1);now1+=d)now++;
           ans=max(ans,now);
           j--;
           k++;
       }
        }
    }
    //cout<=200)
    printf("%d
",ans);
    else printf("No Solution
");
   return 0;
}