Блог пользователя IlyaLos

Автор IlyaLos, история, 9 лет назад, По-русски

659A — Круглый дом

Ответом на задачу является формула ((a - 1 + b) mod n + n) mod n + 1, где mod n — операция взятия остатка по модулю n.

Итоговая временная сложность решения равна O(1).

Допускается также итеративное решение, каждый раз перемещающее Васю на 1 подъезд в нужном направлении.

Итоговая временная сложность решения равна O(|b|).

659B — Отбор на олимпиаду

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

Итоговая временная сложность решения равна .

659C — Таня и игрушки

Наша задача набрать наибольшее количество игрушек, которых ещё нет у Тани так, чтобы их суммарная цена была не больше m. Для этого воспользуемся жадным алгоритмом: будем каждый раз пока нам хватает денег покупать самую дешёвую игрушку, которой ещё нет у Тани. Заведём булевский массив used, чтобы отмечать в нём типы игрушек, которые уже есть у Тани. Очевидно, что на 109 бурлей мы можем купить не более 105 игрушек , а значит нам нет смысла рассматривать игрушки с типами больше или равными 2 × 105 (игрушки таких типов из входных данных будем пропускать) и нам хватит массива used размером 2 × 105. Будем идти по типам игрушек в порядке возрастания пока нам хватает денег и, если в массиве used данный тип отмечен значением \texttt{false}, то будем покупать игрушку этого типа.

Итоговая временная сложность решения составит .

Если вместо булевского массива использовать тип данных <<множество>> (например, \texttt{std::set} в C++), то можно не пропускать большие значения ai из входных данных. В таком случае временная сложность решения составит .

659D — Велосипедная гонка

Из описания трассы следует, что Мария движется таким образом, что вода всегда находится справа от неё. Таким образом, она может упасть в воду только при повороте налево. Для того, чтобы проверить, является ли данный поворот поворотом налево, сопоставим направлениям движения Марии числа: движению на север — 0, движению на запад — 1, движению на юг — 2, движению на восток — 3. Тогда поворот будет поворотом налево, если число для следующего направления dir равно числу предыдущего направления oldDir плюс 1 по модулю 4 (dir ≡ oldDir + 1(mod4)).

Итоговая временная сложность решения равна O(n).

Альтернативное решение. Пусть ответ равен x (это означает, что количество внутренних углов по 270 градусов равно x, а внутренних углов по 90 градусов n - x). Так как сумма внутренних углов n-угольника равна 180 × (n - 2), то можем записать следующее x × 270 + (n - x) × 90 = 180 × (n - 2). Откуда получаем, что . То есть ответ зависит только от n и не зависит от трассы.

Итоговая временная сложность решения равна O(1).

659E — Новая реформа

Во-первых, если граф состоит из нескольких компонент связности, то ответы для них можно считать независимо. Таким образом мы перешли к задаче, когда граф всегда связный. Пусть граф является деревом, тогда мы всегда можем его подвесить и ориентировать все рёбра в порядке обхода dfs'ом. При этом мы сделаем неизолированными все вершины, кроме корня (в подвешенном дереве у каждой вершины, кроме корня, есть единственный предок). Таким образом, ответ в этом случае равен 1. Теперь пусть граф не является деревом, тогда в нём найдётся хотя бы один цикл. Выберем любую вершину на этом цикле и запустим из неё dfs, который ориентирует все рёбра в порядке обхода. Как и в случае с деревом у нас останется только одна изолированная вершина — корень, однако он лежит на цикле и ребро из этого цикла можно ориентировать в него. Таким образом, у нас не останется изолированных вершин и ответ будет равен 0.

Для решения задачи необходимо выделить все компоненты связности и для каждой из них проверить, является ли она деревом. Это можно сделать с помощью dfs или bfs.

Итоговая временная сложность решения равна O(n + m).

659F — Поликарп и сено

В задаче требуется найти связную по сторонам область, произведение количества клеток в которой на минимальное занчение равно заданной величине k. Для этого отсортируем все n × m элементов в порядке невозрастания. Будем последовательно добавлять их в таком порядке, поддерживая при этом компоненты связности. Для этого воспользуемся системой непересекающихся множеств (СНМ, DSU). Кроме того, для каждой компоненты связности необходимо хранить количество клеток в ней. Пусть элемент ai, j только что был добавлен и принадлежит компоненте связности с номеров id. Тогда очевидно, что ai, j — минимум в этой компоненте и если k не делится без остатка на ai, j, то нужной компоненты связности пока получить не удастся. Иначе, посчитаем величину need = k / ai, j — необходимое количество клеток в компоненте связности и если need ≤ CNTid, где CNTid — количество элементов в компоненте связности id, то мы можем найти ответ. Для его поиска запустим из клетки (i, j) dfs, который будет переходить только в клетки больше или равные ai, j и пройдёт ровно need таких клеток.

Итоговая временная сложность решения равна .

659G — Забористое разнообразие

Пусть ответ на задачу — это следующая сумма:

где calc(l, r) — количество способов вырезать верхнюю часть забора так, что её левая граница находится в индексе l, а правая в индексе r. Если l = r (то есть спиливается верхняя часть только одной доски), то calc(l, r) = hl - 1.

Пусть r > l, тогда:

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

Первое слагаемое вычисляется легко, рассмотрим второе слагаемое. Проведём некоторые преобразования:

Обозначим

Рассмотрим, как меняется значение S(r) при увеличении r на единицу:

S(r + 1) = S(r) × min(hr - 1 - 1, hr - 1, hr + 1 - 1) + min(hr - 1, hr + 1 - 1).

Таким образом, эту сумму легко поддерживать перебирая r от 2 до n.

Итоговая временная сложность решения равна O(n).

Разбор задач Codeforces Round 346 (Div. 2)
  • Проголосовать: нравится
  • +85
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

Thanks for nice problems и fast Разбор

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Интересно, почему в задаче D решение работает за O(N), а ограничения на N до 1000?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Если мозг отказался функционировать, как у меня, можно было взять точку, которая на ~0.5 дальше текущего отрезка, и за проверить, лежит ли она внутри многоугольника.

    Вроде очевидная мысль, но мало ли кто не додумался. Как, например, я. Понял эту идею за 4 минуты до конца, быстро написал, без компиляции отправил и... Забыл в цикле одну переменную объявить :)

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Thanks for the lightning speed EDITORIAL.

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

In F problem, I haven't seen the limit that must have an unchanged cell... So I wrote a code in O(sqrt(min(k, 1e15)).. When k > 1e15 print "NO", then enumerate the factor of k, use dsu to solve it, and got WA4. After contest I found the limit and add it then accepted...sad..

»
9 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

The best contest i've seen so far, I really liked the problemset and the fact that is was a 7 problem round instead of the regular one. Great job!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why this 17050130 gets WA in problem E?!!

any one can provide a small case which make it fail ?!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Problem should be solved for every component independently.

    6 6
    1 2
    2 3
    3 4
    4 1
    1 3
    5 6
    
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    I believe this input is a small one where your program fails. There are two connected components: one is a tree and the other is a super well-connected component. The main idea for this test is that the degrees for some vertices are large enough so that when you subtract m edges, then you will not end up with any zeros.

    10 13
    1 2
    1 3
    1 4
    1 5
    1 6
    2 3
    3 4
    4 5
    5 6
    6 2
    7 8
    8 9
    9 10
    
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +26 Проголосовать: не нравится

      Yea, you don't need to read other comments, better post the same idea that i've already posted but with two times bigger test, good job.

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I feel guilty for doing this 17058751 for 659D - Bicycle Race:

  • I simply used java.awt.Polygon class to create the lake polygon.

  • If Maria misses turn i, she would proceed by dx = signum(x(i) - x(i+1)), dy = signum(y(i) - y(i + 1))

  • Then I simply checked if lake polygon contains (x(i) + 0.5*dx, y(i) + 0.5*dy)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hello everyone , Why testcase 53 is not correct in my answer since my answer totally matched with jury answer here is the link... for problem 2

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You have to check if vec[i].size() > 2 before accessing the third element via vec[i][2]. Otherwise you may access unallocated memory. I made the same mistake...

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why does this only seem to fail on test 53? Even the first test case has a region with 2 people.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Suppose size is 2. Then suppose that vec[i][0] = vec[i][1]. Then you will look for vec[i][2] to compare with vec[i][1], but that element might not exist (causing Runtime Error). In samples vec[i][0] > vec[i][1], so you didn't need the third element.

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

There is a parsing error in the editorial of F

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А как можно оценить такую штуку (По задаче F). Количество таких a, что k / a >= n * m. Просто не понимаю, случайность или нет, что решение зашло за O((количество таких а) * n * m)).

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I solved D by finding point inside a polygon . I had to code almost from the scratch because somehow geeksforgeeks code was not working -_- . And after seeing this O(1) solution.....

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Happened with me too !
    I found a working code though ( around 7 lines )

    int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
    {
      int i, j, c = 0;
      for (i = 0, j = nvert-1; i < nvert; j = i++) {
        if ( ((verty[i]>testy) != (verty[j]>testy)) &&
    	 (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
           c = !c;
      }
      return c;
    }
    
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody tell me why i have a WA in test 15 of problem B?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My solution for problem D is to count the number of left turn and the number of right turn then take the minimal of them. I have no idea why it works. It was a desperate attempt. Can somebody provide a proof? Thank you!

My submission: http://codeforces.me/contest/659/submission/17055311

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    My guess is number_of_right_turns = number_of_left_turns + 3

    So number_of_right_turns is always greater than number_of_left_turns.

    You are actually taking number_of_left_turns.

    Just cout << posi << endl; also get AC.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain problem F in more detail please? Basically for each cell with value v, you want to know C(v) = how many cells are connected to it that are at least v. When you sort by decreasing value and DSU, won't your calculation of C(v) for cells with the same value be wrong? For example this grid:

2 4 5

6 4 3

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I didn't notice that in problem D we may only drop into water on left turn and solved the more generalized version of the problem.

The idea is we can record all the vertical and horizontal segments, and for each turning point we can count how many segments we may intersect if we keep going straight. If the count of segments is odd then this point is dangerous, and not while the count is even.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How does that formula come in problem number A ? Can somebody illustrate please ?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Forget the formula. Basically, all you need to do is to make a loop. When the system has 5 rooms, going 6 rooms front actually means going 1 room front, right? For backward movement, 2 rooms back means 3 rooms front. Just keep adding the number of total rooms until you get a non negative number. So taking mod is enough. Just to avoid 0'th position, as 5%5 or 6%6 makes zero, but you want to print 5 or 6, the mod operation is done in two steps. Eventually the -1 with a and the +1 at the end don't make any difference.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In 2nd Problem, why is the output on terminal and Codeforces Judge different??

I got WA on 1st pretest again and again because of this..

My solution is :- http://codeforces.me/contest/659/submission/17065952

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    1) You are doing ios_base::sync_with_stdio(0);

    2) Then read something C-style: scanf("%d %d",&n,&m);

    3) Then read something C++-style: cin>>str>>reg>>score;

    Due to 1), 2) and 3) both read same data. I.e. in 3 you read very first input line instead of second.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hello for problem D, I have a doubt what property does this test case violate:

5
1 1
1 2
-1 2
-1 1
1 1
»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

First of all, thank you for the quick editorial!! I would like to mention 2 points regarding the editorial:

  1. The phrase "as soon as" is used in places where "since" or simply "as" should be used. It is not that important(since the intention is very much clear), but feels odd! :P

  2. For problem E, I did not understand the part "...as chosen vertex belongs to a cycle, at least one of its edge will not be taken to account in the DFS, so it can be given to a root. This way all the vertices will be satisfied." clearly. Can someone explain it in more details?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is perhaps slightly misworded. The key idea is that for any tree, we can pick any root and direct each of the edges so that only the chosen root of the tree is unaccessible. Therefore, if the program finds a cycle in a connected component, and we assign the root to any node of the cycle then one can perform the same algorithm, except this time there will be one extra edge incident to the picked root (otherwise, the cycle wouldn't exist). This extra edge can, of course, be directed to make the root accessible as well, thereby solving the problem.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      So, in short, does this mean the following?

      1. The final answer is the sum of the answers for each individual connected component.

      2. For a connected component, the answer is 1 if the component is a tree, 0 otherwise.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

У меня небольшая проблема с задачей C. Мои локальные результаты отличаются от результатов теста CF.

Локальный результат
Результат теста CF

http://codeforces.me/contest/659/submission/17051531 — код

C++ я начал изучать недавно, может кто, пожалуйста, объяснить новичку в чем здесь проблема?

Заранее спасибо!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Переменная p не инициализирована. Совет: инициализировать все переменные сразу после объявления. Т.е. не писать int a, b, c, d, а писать int a = 0, b = 0, c = 0, d = 0.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can any one tell why am i getting RTE on problem B

this my submission

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Good day to you man!

    The RTE is because of sort :'( you have to change comparator:

    bool cmp(pair<string, int>s1, pair<string, int> s2) {
        if (s1.second >= s2.second)
            return false;
        return true;
    }
    

    like this :)

    +btw I'm convinced the part at the end is also wrong :/

    I would change it like:

    REP(i, 1, m + 1) {
            int size = mat[i].size();
            if (size==2||mat[i][size - 2].second != mat[i][size - 3].second) {
                size--;
                if (size - 2 >=0 ) {
                    if (mat[i][size - 1].second != mat[i][size - 2].second) {
                        cout << mat[i][size ].first << " " << mat[i][size - 1].first << endl;
                        continue;
                    }
                } else {
                    cout << mat[i][size ].first << " " << mat[i][size - 1].first << endl;
                    continue;
                }
            }
            cout << "?" << endl;
        }
    
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thnx !! it worked !! but i can't understand why RTE ?!

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Well, sort comparator must be deterministic.

        That means it must decide (in finite time) for each pair of elements, whether one of them is bigger (and which one) or whether they are equal.

        a: A < B && !(B < A) means A < B

        b: !(A < B) && B < A means A > B

        c: !(A < B) && !(B < A) means A == B

        anyway A<B && B<A (which could have been returned in your program) is "nothing" so the function could not determine, how to sort it :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain solution for F in more details ?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem G has a divide and conquer solution too ... :P *I wanst able to arrive at the formula stated in the editorial but divide and conquer was a bit more intuitive to me *

Link to submission- http://codeforces.me/contest/659/submission/17075860

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone explain solution of problem E in detail.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Every connected component of the graph, could be solved independently. Each connected component has at most 1 vertex with ending degree 0 after all (solving optimally) . If the connected component is a simple path or a tree root on a vertex v, we may notice that this component has 1 vertex with ending degree 0. If the connected component is cyclic, starting on any node we can organize the Edges in order to take no edges with ending degree 0. Imagine we have one conected component witch has a cycle and a path or a cycle and a tree or both :) , for example this: 1-2, 2-3, 3-1, 1-5, 5-6; Notice we can turn it into the problema of the cyclic connected componen. For this, we can also pick the vertex with in-out degree=1 and connect it. For example: 1-2 , 2-3 , 3-1, 1-5 5->6; 1-2,2-3,3-1, 1->5, 5->6; In this phase we have the same cycle! Therefore, we can run a dfs for each connect component and verify if it has any cycle. If it has add the answer by 1, if it has not, add the answer by 0.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If it has a cycle, we should not add 1 to the answer right? your last two lines confuse me

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В задаче F зашел DFS от каждой "подходящей" точки, то есть по сути O(m * n * n), где m — это количество — делителей k, которые у нас есть в таблице и при этом с их помощью можно получить объем k. Долгое время в max-тесте был TL, потому что неудачно занулял массив used вершин для DFS. После AC появился вопрос: Количество делителей равное ~3000 это максимум для данных ограничений задачи?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      У меня его решение падает на тесте, созданном этим генератором. Можете проверить это на сервере? В запуске проверить не могу, т.к. тест больше 256 кб получается

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Нет, при k = 121645100408832000 будет 16760 делителей

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks. Some beautiful problems and elegant solutions out there. :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There is O(1) solution for problem E. http://www.codeforces.com/contest/659/submission/17067296 Can anyone explain me this.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's not a real solution. It exploits the fact that many tests cases share the same solution and compares number of nodes, edges and first number in second line to identify the test case and print the solution accordingly.

    You can easily hack it! ;)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please it would be really grateful if someone can explain editorial of Problem F.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    You just need to launch dfs from all i and j that k % a[i][j] = 0 and k / a[i][j] <= n * m. In dfs count values that v >= a[i][j]. if value equals to k / a[i][j] you could find answer.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Thanks I got your point but if we launch dfs from each i and j for the mentioned condition, won't the complexity be O(n*m*(n*m)) in worst case? How to make it efficient?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem G

please explain how S(r + 1) = S(r) × min(hr - 1 - 1, hr - 1, hr + 1 - 1) + min(hr - 1, hr + 1 - 1).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

O(1) for bicycle race its superb

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem E

why N — BPM getting WA?

Graph :

Edge 1 | Node1

Edge 2 | Node2

Edge 3 | Node3

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

83363813 can anyone provide a smaller test case where my sol fails

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sorry, I am too late but in problem E, what about individual components with no roads why we have to add 1 as I was getting WA earlier but question states a city is separate only when it has no road leading into it and only leading out of it.

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My hand at a more "human" explanation for problem G from someone bad at maths:

First, let's solve this task for constant h[i] (assuming each element of h is reduced by 1 from now on).

If we only consider the first plank, we can cut off any part of plank 0 from 1 to h[0]. The total answer for this plank is h[0] — dp[0] = h[0].

If we consider the second plank, we can either only cut off part of plank 1 from 1 to h[1], or do the same in addition to any possible cutoff ending at the previous plank (it's clear that no matter whether we cut off 1 or h[1], we still can cut off any part of h[0]). The answer for this plank is h[1]+h[1]*h[0], and the total answer is h[0]+h[1]+h[1]*h[0].

We can advance infinitely, storing the answer for the previous plank:

dp[i] = h[i] + h[i] * dp[i-1]
ans = sum(dp)

Now let's consider the case where h[i] is non-decreasing.

The start is obviously the same, but things change starting from the second plank.

If we want to cut h[1] but leave h[0] (and everything before) as-is, nothing changes for us, so h[i] is still part of dp[i].

But if we want to also cut off part of h[0] and h[0] < h[1], then we can only cut off any part of h[0] if we also cut h[1] to the same height as we will cut h[0]. For example, if h[0] = 3 and h[1] = 10, we can cut h[0] and h[1] to length 0, length 1 or length 2, but cutting h[1] to length 3 makes h[0] impossible to cut.

This means that in this case:

dp[0] = h[0]
dp[i] = h[i] + min(h[i], h[i-1])*dp[i-1]
ans = sum(dp)

Finally, let's consider the hardest case — non-increasing sequences.

If we want to cut off h[0] alongside h[1] and h[0] > h[1], then we can only cut h[0] to the same or smaller height as h[1]. If h[0] = 10 and h[1] = 2, we can cut h[1] to 0 (in which case h[0] must be cut to 0 as well), or we can cut h[1] to 1 (in which case h[0] can be cut to either 0 or 1). In addition, all options that depend on h[0] being higher than h[1] are unreachable from h[1].

So in this case, only part of dp[i-1] must be used — instead of dp[i-1], use the same formula as before dp[i-1] but with changed height:

calc_dp(0, height) = height
calc_dp(i, height) = height + min(height, h[i-1]) * calc_dp(i-1, min(h[i-1], h[i]))
dp[i] = calc_dp(i, h[i])
ans = sum(dp)

Or, to put it in a different way:

# h2 is needed to account for increasing sizes (h[i]<h[i+1])
h2[i] = min(h[i-1], h[i])
# dp2 is needed to account for decreasing sizes
# dp2[i]: how many options ending at plank i are reachable from plank i+1
dp2[0] = h2[1]
# specifically min(h2[i], h[i+1]) on the next line is needed to account for decreasing sizes, otherwise dp2 is equivalent to dp
dp2[i] = h2[i+1] + dp2[i-1] * min(h2[i], h[i+1])
# dp[i]: how many options end at plank i
dp[0] = h[0]
dp[i] = h[i] + dp2[i-1] * h2[i]
ans = sum(dp)

Still pretty convoluted, but hopefully a bit easier to understand. See 223426302