Решение задачи Отрезок Фибоначчи с Codeforces

С пояснением   Просмотров: 1186

Дан массив a 1, a 2, ..., a n. Отрезок [l, r] (1 ≤ l ≤ r ≤ n) называется хорошим, если a i = a i - 1 + a i - 2, для всех i (l + 2 ≤ i ≤ r).

Определим функцию len([l, r]) = r - l + 1, len([l, r]) называется длиной отрезка [l, r]. Отрезок [l 1, r 1], длиннее отрезка [l 2, r 2], если len([l 1, r 1]) > len([l 2, r 2]).

Требуется найти в массиве a хороший отрезок наибольшей длины. Заметьте, что отрезок, длины 1 или 2 всегда хороший.

Код 

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,ans=2,temp=2;
	cin>>n;
	int a[n];
	cin>>a[0]>>a[1];
	for(int i=2;i<n;i++)
	{	cin>>a[i];
		if((a[i-1]+a[i-2])==a[i])
			{ans++;
			if(ans>temp)
				temp=ans;
			}
		else
			{ans=2;
			}
	}
	if(n>=2)
		cout<<temp;
	else
		cout<<n;
	return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Хороший отрезок либо содержит все нули, либо длина его мала. Второе следует из того, что длина отрезка не может превосходить длины последовательности {0, 1, 2, 3, 5, 8, ..., x, y} ( y > 109; x < 109). Длина этой последовательности, в свою очередь, меньше 50. Тогда второй случай можно разобрать наивным алгоритмом, а второй, например, динамикой ( d i = 0 eсли a i ≠ 0 и d i = d i - 1 + 1 если a i = 0).


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp