Костя решил создать свою первую мобильную игру, и, разумеется, он хочет начать с реалистичной физики. Поскольку Костя еще маленький, совсем реалистичная физика ему дается плохо, так что он выбрал упрощенный вариант. Уровень в его 2D игре представляет собой участок земли шириной n пикселей, где земля в i-м столбце занимает нижние ai пикселей, а все, что выше — занято воздухом. Иногда в Костиной игре идет дождь, и тогда вода заполяет пространство по правилам реального мира, занимая все пространство, из которого не может вылиться ни налево, ни направо.Вам дано описание уровня в игре, ваша задача — определить какой объем уровня (в пикселях) будет заполнен водой.Входные данныеВ первой строке ввода задано число n — ширина уровня (1⩽n⩽106В следующей строке через пробел перечислены числа ai — высоты земли в каждом столбце пикселей (0⩽ai⩽109).Выходные данныеВыведите единственное число — количество воды (в пикселях), которое будет на уровне после дождя.Примерывходные данные84 2 3 1 5 2 3 1выходные данные7входные данные41 3 7 2выходные данные0ПримечаниеСчитайте, что дождь идет достаточно долго, чтобы уровень воды установился на возможном достижимом максимуме в каждом столбце и больше не менялся.Можете написать идею алгоритма или код (желательно на плюсах)

какой там 2 вапроса или 1?

дан ряд чисел:

1 2 3 4 5 6 7 8 9 10 11

рассмотрим наихудший вариант попадания

1. говорим цифру 2, в ответ ничего не слышим, соответственно в 1 и 3 тоже ничего нет

2. говорим цифру 5, в ответ ничего   не слышим, соответственно в 4 и 6 тоже ничего нет

3. говорим цифру 8, в ответ ничего   не слышим, соответственно в 7 и 9 тоже ничего нет

4. говорим цифру 10, в ответ слышим "попал" или "почти попал", и сразу становится понятно, где цифра.

если слышим раньше "попал", то на этом останавливаемся.

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

ответ: 4 - наименьшее количество чисел при худшем раскладе.

//у меня прошел все тесты

#include < iostream>

#include < vector>

#include < algorithm>

using namespace std;

int abc(int a)

{

    if(a > 0)

        return a;

    return a *= -1;

}

int main()

{

  int n;

    cin> > n;

    vector< int> d(n+1);

//ввод

    for(int i = 1; i< =n; i++)

    {

        cin> > d[i];

    }

    vector< int> b(n+1);

    b[1] = d[1];

    b[2] = abc(d[2] - d[1]);

//дп

    for(int i = 3; i< =n; i++)

    {

      long a = abc( d[i] -   d[i-1] );

        long z =   abc( 3 *   (   d[i]   -   d[i-2]   ) );

        a = a   + b[i-1];

        z =   z   + b[i-2];

        b[i] = min(a,z);

      // cout< < b[i]< < " "< < i< < endl;

        if(i == 3 & & b[i] == z)

        {

            b[i] -= d[i-2];

        }

  }

    cout< < b[n]< < endl

}