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

{{Problem C :- Barcode}}{{Codeforces Round 139 DIV 2}}
Автор sameer_hack, история, 6 лет назад, По-английски

I am trying to solve this problem and I am not able to understand the editorial that why
dp[0][i]=min(dp[1][i-a]+sum-of-whites(i-a+1,i))
dp[1][i]=min(dp[0][i-a]+sum-of-blacks(i-a+1,i))
where a belongs to [x,y]
Editorial Link :- Editorial
Question Link :- Question

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

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

Can anybody from community can help with me this question ? Its been 7hrs and I dont know why people doesnt respond to question that may look small to you but its like mount Everest for me. :/

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

    dp[c][i] — minimal cost of painting the first i columns in NxM rectangle into a barcode the way its last stripe will be (c == 0 ? black : white).

    dp[0][i]=min(dp[1][i-a]+sum-of-whites(i-a+1,i))

    This line checks if it is optimal to paint last a lines in black.

    dp[1][i]=min(dp[0][i-a]+sum-of-blacks(i-a+1,i))

    And this line checks if it is optimal to paint last a lines in white.

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

      Can you please explain how the two recurrence relation is formed ?

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

        Well, let's look on Nxi rectangle formed with the first i columns. What can we say about its last stripe? Either it's black or white and his width is ranged from x to y. Therefore, we handle 2 * (y — x + 1) variants. Let's imagine the last stripe in your subrectangle is white. It means that previous stripe's color has to be the different (black). Then, for each a x <= a <= y check the cost of oainting rectangle Nx(i-a) in stripes so it will end with the black stripe (dp[0][i-a])and add the cost of painting columns from i-a+1 to i in white (sum-of-whites(i-a+1,i)). Then we keep the best outcome.

        Same thing with the case, where the last stripe in rectangle Nxi is white, but with reverse colouring.

        → Ответить