Решение задачи Планирование путешествия с Codeforces

Без пояснения   Просмотров: 69


Таня запланировала путешествие по городам Берляндии. Всего в Берляндии n городов, расположенных вдоль главного железнодорожного пути. Города пронумерованы от 1 до n.

План путешествия Тани выглядит следующим образом: для начала она выбирает город c1, с которого она начнет путешествие. Она посещает его, а затем отправляется в другой город c2>c1, затем в следующий город c3>c2, и так далее, пока не решит закончить свое путешествие в некотором городе ck>ck−1. Таким образом, последовательность посещенных городов [c1,c2,…,ck] должна быть строго возрастающей.

На последовательность посещенных городов есть еще одно ограничение. Город i имеет красоту bi. Если Таня решит посетить только один город, красоты городов не накладывают никаких дополнительных ограничений; однако если она решила посетить несколько городов, то для каждой пары соседних городов ci и ci+1 в плане должно выполняться условие ci+1−ci=bci+1−bci.

Например, если n=8 и b=[3,4,4,6,6,7,8,9], следующие планы путешествия корректны:

c=[1,2,4];
c=[3,5,6,8];
c=[7] (путешествие, состоящее из одного города, считается корректным).
Также существуют другие планы посещения городов, не описанные выше.

Таня хочет, чтобы ее путешествие было максимально красивым. Красота путешествия равна суммарной красоте всех посещенных городов. Можете ли вы составить план путешествия, максимизирующий суммарную красоту посещенных городов?


Код

#include<bits/stdc++.h> 
using namespace std;
int main()
{
	map<long long,long long>a;
	long long n,k,m=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>k;
		a[k-i]+=k;
		m=max(m,a[k-i]);
	}
	cout<<m<<endl;
	return 0;
}

         

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



Комментарии

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