Can anyone help me with this dynamic programming problem. The problem is 225C - Barcode. I can't get the solution from editorial.
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 162 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 154 |
8 | pajenegod | 147 |
9 | BledDest | 145 |
9 | Um_nik | 145 |
Can anyone help me with this dynamic programming problem. The problem is 225C - Barcode. I can't get the solution from editorial.
Name |
---|
First of all, we construct array of partial sums to calculate amount of pixels in some columns of some color in O(1). Let it be array w[]. w[i] — amount of white pixels in columns [1..i]. For each column we calculate amount of white pixels in it. Then,
w[0]=0; w[i]=w[i-1]+amount_of_white_pixels_in_column_i;
Example:Now,
amount_of_white_pixels_in_columns [i..j] = w[j]-w[i-1];
amount_of_black pixels_in_columns [i..j] = (j-i+1)*N - amount_of_white_pixels_in_columns [i..j];
Now, lets build dp solution.
dp[0][0] = dp[1][0] = 0
— obvious answer for zero columns.amount_of_white_pixels_in_columns [j-a+1..j]
(see first part) white pixels. Also, we need re-paint columns [1..j-a] so that column j-a is white. This is dp[1][j-a]. Similarly calculate dp[1][j]min(dp[0][M], dp[1][M])
Feel free to ask if you cannot understand something.
So, you are given a nxm pixel picture. Now, you need to make a barcode picture by changing minimum number of pixels .
For a certain column you will either change every pixel of that column into black or white.To make every pixel of that column black : cost = number of white pixel of that column and vice versa.
now suppose you are in Kth column. Now dp[0][K] means minimum number of pixels needed to make a barcode picture and the color of last bar is Black(width of last bar can be x to y). And we only got the ans for 1 to Kth column.
So, to minimize complexity precompute. Let, preBlack[I][J] means number of Black pixels from Ith column to Jth column.
preWhite[I][J] is vice versa . Complexity : nm
now iterate through every column for every column take the minimum ans from all possible width of last bar and save ans.
for(I=1;I<=m;I++){
int Min1=inf,Min2=inf;
for(J=x;J<=y;J++){
}
dp[0][I]=Min1;
dp[1][I]=Min2;
}
Now the ans will be min( dp[0][m] , dp[1][m] );
Think about it a little bit.
but what if j > i
I guess He forgot to apply this condition. Increase j till it reaches minimum of i and y
Thank you very much