[PROBLEM] The Chocolate Bar
source link: https://codeforces.com/blog/entry/103999
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
You are given a chocolate bar represented as a grid of size x, find the number of ways you can finish the chocolate bar by eating it.
When eating the chocolate bar, each time, you remove one block from the grid which is not surrounded by another chocolate block which has not been eaten yet from all 4 directions
Example : Consider the x chocolate bar below, corners colored in Dark Brown and the center in Red, every chocolate block is accessible to be eaten in the very beginning except the center, it becomes accessible if at least on the corners was eaten
What is the best complexity that can be achieved in terms of ? and how?
Edit : Sorry for not mentioning that, but the best solution I have came up with myself so far is bitmask dp in
|
i dont know if you are still looking for an answer, but i found a solution here https://blog.csdn.net/wozaipermanent/article/details/77920306 the main idea is to create a 3d array of f[][][] and first fill in the obvious stuff. then iterate over the i and j (n and m) and then k, in order from smaller bars, and then bigger bars. it is done by kind of reversing the cut, which means, imagine merging two smaller pieces. a piece can be merged horizontally or vertically, and when filling a space f[i][j][k] you are taking two smaller pieces, each with k-kk and kk pieces already in it with added cost of length of cut squared, and then take the smallest cost from the existing and the new merge. this way you are effectively exploring all the possible cuts, which is why there is a tag "brute force" in this problem. this solution works reasonably well, because of fairly small data (n and m <= 30 and k <= 50) edit: i just checked how many operations it takes for this code to run, i changed the comparisons to val += 1, and the val i got at the end was 16,996,384. so it is well under time requirement. |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK