NOIP模拟题 斐波那契数列

题目大意

给定长度为$n$序列$A$，将它划分成尽可能少的若干部分，使得任意部分内两两之和均不为斐波那契数列中的某一项。

题解

不难发现$2\times 10^9$之内的斐波那契数不超过$50$个

先求出第$i$个数之前最后一个能和第$i$个数相加为斐波那契数的位置$last_i$。

考虑每一部分$[l,r]$只需满足$\max\{last_i\}<l(i\in [l,r])$即可。

那么设$F_i$表示以$i$为结尾最小化分数，那么转移到$i$的$j$显然是一段左右端点均单调不递减的区间，用单调队列维护即可。

#include<bits/stdc++.h>

#define debug(x) cerr<<#x<<" = "<<x

#define sp <<"  "

#define el <<endl

#define LL long long

#define M 100020

#define MAXN 2000000000

using namespace std;

int read(){

	int nm=0,fh=1; char cw=getchar();

	for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;

	for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');

	return nm*fh;

}

map<int,int>MP; int n,m,p[M],F[M],last[M],G[M],q[M],hd,tl;

int main(){

	G[1]=1,G[2]=2,F[1]=1; n=read();

	for(m=2;(LL)G[m-1]+(LL)G[m]<=MAXN;m++) G[m+1]=G[m]+G[m-1];

	for(int i=1;i<=n;i++) p[i]=read();

	MP[p[1]]=1,q[tl++]=0,q[tl++]=1;

	for(int i=2,now=0;i<=n;i++){

		last[i]=0;

		for(int j=0;j<=m;j++){

			if(!MP.count(G[j]-p[i])) continue;

			int k=MP[G[j]-p[i]]; last[i]=max(last[i],k);

		} now=max(now,last[i]);

		while(q[hd]<now) hd++; F[i]=F[q[hd]]+1,MP[p[i]]=i;

		while(F[q[tl-1]]>=F[i]&&hd<tl) tl--; q[tl++]=i;

	}

	printf("%d\n",F[n]);

	return 0;

}