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

how to prove that a dp solution state is wrong in general?
Автор WinstonWolf, история, 7 лет назад, По-английски

I'm stuck in this problem 225C - Barcode

Here is my solution 33821210

I tried to calculate the array dp[current_column][width_of_current_group][hash_or_dot], and after i read the tutorial saying that i should calculate only dp[current_column][hash_or_dot] i didn't figure out why my solution was wrong.

I think they are the same, can't see any difference... can somebody help?

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

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

Auto comment: topic has been updated by WinstonWolf (previous revision, new revision, compare).

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

Both solutions have the same idea .. but yours uses more memory in vain. So either there's a bug in your code or you have a wrong dp state.

We have dp[pos][type][how_much] means that you're in the [pos] column and now you're trying to fill it with [type] (white or black) and you have [how_much] of them from previous columns, and it returns the minimum possible of pixels to repaint till the end.

dp[pos][type][how_much] = dp[pos + 1][type][how_much + 1] + arr[pos][type ^ 1]

And if (x <= how_much <= y) dp[pos][type][how_much] = min(dp[pos][type][how_much], dp[pos + 1][type ^ 1][1]+arr[pos][type]);

Where arr[pos][type] refers to number of white or black pixles in the column [pos].

So the answer is min(dp[0][1][0], dp[0][0][0]).

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

The following submission using C++ STL arrays and based on the problem tutorial may help you to improve the readability and efficiency of your solution.

33832273

Please note that computing the number of black and white pixels between columns 1 and j inclusive is done prior to the DP main loop. The result is then used to compute the number of black and white pixels between columns j and i inclusive in O(1) time using a simple subtraction operation.

Best wishes

→ Ответить