Помогите сделать задание на с++.

Question

Помогите сделать задание на с++.

Ирина Ученик (190), на голосовании 1 год назад

Дом, который построил Джек
Вот дом, который построил Джек. Дом состоит из n комнат, расположенных в один ряд. Джеку не по душе, что его пшеница, которая в темном чулане хранится, хранится в темном чулане, ведь он находится за пределами дома, и фермер не может должным образом следить за ней. Поэтому Джек решил выделить ей несколько комнат дома, расположенных вдоль длинного коридора. Для удобства пронумеруем комнаты целыми числами от 1 до n . Каждая комната имеет свой уровень комфорта ai . Джек собирается выбрать последовательность подряд идущих комнат и переместить в них всю пшеницу. Джек — хороший фермер, а потому хочет, чтобы пшеница находилась в комнатах с максимально возможным суммарным уровнем комфорта. Помогите Джеку выбрать подходящую последовательность комнат, а также скажите сколько существует способов это сделать.

Дополнен 1 год назад

Формат входных данных
Первая строка содержит одно целое число n
(1≤n≤300000
) — количество комнат в доме Джека.

Вторая строка содержит n
целых чисел ai
(−109≤ai≤109
) — уровни комфорта в комнатах дома.

Формат выходных данных
Выведите два целых числа — максимальный суммарный уровень комфорта в выбранных комнатах, а также количество способов выбрать последовательность комнат с максимальным уровнем комфорта.

Answer 1

Эта задача может быть решена с использованием методики динамического программирования.

1. Сначала мы создаем два вектора: один для хранения суммы уровня комфорта, другой для хранения количества способов получить эту сумму.

2. Затем мы идем по комнатам и обновляем эти векторы, учитывая уровень комфорта каждой комнаты.

3. В конце мы выбираем комнату с максимальной суммарной комфортностью и смотрим, сколько способов есть получить эту комфортность.

Вот пример кода на C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
int n;
cin >> n;

vector<int> comfort(n);
for (int i = 0; i < n; ++i) {
cin >> comfort[i];
}

vector<long long> sum(n+1, 0);
vector<long long> ways(n+1, 0);

sum[0] = 0;
ways[0] = 1;
for (int i = 1; i <= n; ++i) {
sum[i] = max(sum[i-1], comfort[i-1] + (i > 1 ? sum[i-2] : 0));
if (sum[i] == sum[i-1])
ways[i] = (ways[i] + ways[i-1]) % MOD;
if (sum[i] == comfort[i-1] + (i > 1 ? sum[i-2] : 0))
ways[i] = (ways[i] + (i > 1 ? ways[i-2] : 1)) % MOD;
}

cout << sum[n] << " " << ways[n] << endl;
return 0;
}

В этом коде переменная `sum` содержит максимальную сумму комфортности для каждой комнаты, а `ways` содержит количество способов достижения этой суммы. Затем мы проходим по каждой комнате и обновляем эти две переменные в соответствии с уровнем комфортности комнаты. В конце код выводит максимальную сумму комфортности и количество способов достижения этой суммы.