Задача

Вы – профессионал своего дела и планируете ограбить ряд домов вдоль улицы. В каждом доме спрятана определенная сумма денег. Единственное, что мешает Вам грабить – так это то, что соседние дома связаны системой безопасности: будет передан сигнал в полицию, если два соседние дома будут ограблены в один и тот же вечер.

Зная количество денег в каждом доме, определите максимальную сумму, которую Вы сможете ограбить сегодня вечером без уведомления полиции.

Входные данные

Первая строка содержит количество домов $n (1 \leqslant n \leqslant 10^6)$. Вторая строка содержит n целых неотрицательных чисел $a_1, a_2, …, a_n$, где $a_i$ — количество денег, которое может быть вынесено из iго дома.

Выходные данные

Выведите максимальную сумму, которую Вы сможете ограбить сегодня вечером без поступления сигнала в полицию.

Тесты

№	Входные данные	Выходные данные
1	5 6 1 2 10 4	16
2	10 4 1 29 0 14 8 31 12 7 5	85
3	2 1 3	3

Код

#include <iostream>
 
using namespace std;
 
void houseRobbery(int houseCount, unsigned long *maxSum, unsigned long *initialHouses) {
    /*
    A function that, through dynamic programming, calculates the maximum production of houses not standing nearby.
    The function does not return anything, since it modifies arrays through pointers
    */
    
    // Initial state values from first two houses
    maxSum[0] = initialHouses[0];
    maxSum[1] = max(initialHouses[0], initialHouses[1]);
 
    // Since by condition it is given that we cannot rob two houses in a row, 
    // then we will take the maximum house of two: maxSum[i - 1] and maxSum[i - 2] + initialHouses[house] 
    // (where initialHouses[house] is the amount of money in the i-th house)
    for (int house = 2; house < houseCount; house += 1) {
        maxSum[house] = max(maxSum[house - 1], maxSum[house - 2] + initialHouses[house]);
    }
}
 
int main() {
    int houseCount;
    cin >> houseCount;

    // Initialize the arrays not containing negative values
    unsigned long initialHouses[houseCount], maxSum[houseCount];
 
    // Filling the initial array of houses with user input
    for (int element = 0; element < houseCount; element += 1) {
        cin >> initialHouses[element];
    }
    
    // Calling the function
    houseRobbery(houseCount, maxSum, initialHouses);
 
    cout << maxSum[houseCount - 1];
    return 0;
}

#include <iostream>

using namespace std;

void houseRobbery(int houseCount, unsigned long *maxSum, unsigned long *initialHouses) {

A function that, through dynamic programming, calculates the maximum production of houses not standing nearby.

The function does not return anything, since it modifies arrays through pointers

// Initial state values from first two houses

maxSum[0] = initialHouses[0];

maxSum[1] = max(initialHouses[0], initialHouses[1]);

// Since by condition it is given that we cannot rob two houses in a row,

// then we will take the maximum house of two: maxSum[i - 1] and maxSum[i - 2] + initialHouses[house]

// (where initialHouses[house] is the amount of money in the i-th house)

for (int house = 2; house < houseCount; house += 1) {

maxSum[house] = max(maxSum[house - 1], maxSum[house - 2] + initialHouses[house]);

}

int main() {

int houseCount;

cin >> houseCount;

// Initialize the arrays not containing negative values

unsigned long initialHouses[houseCount], maxSum[houseCount];

// Filling the initial array of houses with user input

for (int element = 0; element < houseCount; element += 1) {

cin >> initialHouses[element];

}

// Calling the function

houseRobbery(houseCount, maxSum, initialHouses);

cout << maxSum[houseCount - 1];

return 0;

}

Решение

Данная задача, это типичный пример применения динамического программирования.
Динамическое программирование — это метод решения задачи путём её разбиения на несколько одинаковых подзадач, рекуррентно связанных между собой.

Решение задачи динамическим программированием должно содержать следующее:
— Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям, либо к задаче, решаемой элементарно.
— Зависимость элементов динамики друг от друга. Такая зависимость может быть прямо дана в условии. В противном случае вы можете попытаться узнать какой-то известный числовой ряд, вычислив первые несколько значений вручную.

Для решения данной задачи будет использовать метод последовательного вычисления (далее МПВ).
МПВ подходит, только если функция ссылается исключительно на элементы перед ней — это его основной минус.
Суть метода в следующем: необходимо создать массив на N элементов и последовательно заполнять его значениями. Таким образом вычисляется, в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения.

Зная, что такое динамическое программирование и МПВ — можно описать алгоритм решения.
Пусть $a_i$ — количество денег в $i$-ом доме и houseRobbery(i) — максимальное количество денег, которое удалось унести грабителю.

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

Далее в цикле рассматривается $i$-й дом и определять для него $houseRobbery(i)$, где houseRobbery(i) — максимальное из houseRobbery(i - 1) и houseRobbery(i - 2) + initialHouses[i], так как нужно учитывать houseRobbery(i - 1), если $i$-й дом не был ограблен, а houseRobbery(i - 2) + initialHouses[i], если $i$-й дом — ограблен.

И так как используется МПВ, то последний элемент в заведенном массиве и будет решением этой задачи.

Ссылки

Related Images:

Тесты

№

Входные данные

Выходные данные

Объяснение

2 2

1 100

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

50 100

53 59 61 67 71 73 79 83 89 97

10 2

Неправильно, так как противоречит условию ($a \leqslant b$)

99900 100000

99901 99907 99923 99929 99961 99971 99989 99991

-15 -6

-13 -11 -7

Неправильно, так как противоречит условию ($1 \leqslant a \leqslant b \leqslant 100000$)

Код

#include <iostream>
#include <cmath>

using namespace std;


bool eratosthenesSieve(int currentNumber) {
    /*
    Describe the function that checks if the number is prime and returns a boolean value.
    This function is based on the "sieve of Eratosthenes" algorithm.
    True - if the number is prime, false - normal.
    */
    
    // If the number equals to 1 or if it even, return false. And if it equals to 2, return true.
    if (currentNumber == 2 or currentNumber == 3) {
        return true;
    } else if (!(currentNumber % 2) or !(currentNumber % 3) or currentNumber == 1) {
        return false;
    }
    
    // If the number has the divider from 5 to the root of this number with the second step return false.
    for (int divider = 5; divider <= sqrt(currentNumber); divider += 2) {
        if (!(currentNumber % divider)) {
            return false;
        }
    }
    
    // In all other situations, return true.
    return true;
}


void printSequenceOfPrimeNumbers(int beginning, int ending) {
    /*
    This function prints all prime numbers in a line.
    It contains a loop that starts and ends with the given values.
    */

    for (int sequenceElement = beginning; sequenceElement <= ending; sequenceElement += 1) {
        if (eratosthenesSieve(sequenceElement)) {
            cout << sequenceElement << " ";
        }
    }
}


int main() {
    /*
    Receive the beginning and end of the sequence.
    */
    
    int beginning, ending;
    cin >> beginning >> ending;
    
    // Calling the function.
    printSequenceOfPrimeNumbers(beginning, ending);

    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

bool eratosthenesSieve(int currentNumber) {

Describe the function that checks if the number is prime and returns a boolean value.

This function is based on the "sieve of Eratosthenes" algorithm.

True - if the number is prime, false - normal.

// If the number equals to 1 or if it even, return false. And if it equals to 2, return true.

if (currentNumber == 2 or currentNumber == 3) {

return true;

} else if (!(currentNumber % 2) or !(currentNumber % 3) or currentNumber == 1) {

return false;

}

// If the number has the divider from 5 to the root of this number with the second step return false.

for (int divider = 5; divider <= sqrt(currentNumber); divider += 2) {

if (!(currentNumber % divider)) {

return false;

}

// In all other situations, return true.

return true;

}

void printSequenceOfPrimeNumbers(int beginning, int ending) {

This function prints all prime numbers in a line.

It contains a loop that starts and ends with the given values.

for (int sequenceElement = beginning; sequenceElement <= ending; sequenceElement += 1) {

if (eratosthenesSieve(sequenceElement)) {

cout << sequenceElement << " ";

}

int main() {

Receive the beginning and end of the sequence.

int beginning, ending;

cin >> beginning >> ending;

// Calling the function.

printSequenceOfPrimeNumbers(beginning, ending);

return 0;

}

Решение

Решето Эратосфена это алгоритм поиска простых чисел.
Решение данной задачи сводится к тому, чтобы воплотить данный алгоритм. По мере прохождения перечня, нужные числа остаются, а ненужные (составные) исключаются.

Это решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых.

Рассуждение:
— Все четные числа, не считая двойки, — составные, то есть не являются простыми, так как делятся не только на себя и единицу, а также еще на $2$.
— Все числа кратные трем, кроме самой тройки, — составные, так как делятся не только на самих себя и единицу, а также еще на $3$.
— Число $4$ уже выбыло из игры, так как делится на $2$.
— Число $5$ простое, так как его не делит ни один простой делитель, стоящий до него.
— Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

В моем коде, указанном выше, была реализована функция-фильтр, которая, по большей части, реализовывает метод перебора делителей и проверяет: есть ли делители числа, кроме его самого, вплоть до корня из этого числа. И если остатки от деления не равны $0$, то мы возвращаем истину, что означает: число простое.

Таким же образом, проверяем все остальные числа из промежутка от $n$ до $m$ и выводим полученную последовательность на экран.