| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | -is-this-fft- | 148 |
| 5 | atcoder_official | 148 |
| 5 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 9 | TheScrasse | 144 |
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?
Auto comment: topic has been updated by WinstonWolf (previous revision, new revision, compare).
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]).
Thanks for your help :)
It was one silly fault in my implementation :"D
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
1andjinclusive is done prior to the DP main loop. The result is then used to compute the number of black and white pixels between columnsjandiinclusive in O(1) time using a simple subtraction operation.Best wishes