Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

difask's blog

DP problem
By difask, 10 years ago, In English

Hello everyone! Please, help me to solve dp problem. We have matrix n*m and house a*b. On some cells there are trees. So we cannot build house on trees. We should count how many ways exist to build one house.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Main idea is to check does __i, j position can be down right corner, which means that you have height __i with no trees and width __j with no trees. Whole dp point is saving how much trees you have above and how much trees you have left from current position. Obviously that can not guarantee if there is tree on diagonal, so you need to do aditional checks.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it's pretty easy — for each cell check whether it can be top left corner of AxB rect. or not. It can be done in linear time — firsly, count prefix sums A, such that S[i][j] = number of tress in rect. (1, 1) _ (i, j) (count this using some ez dp ideas) . Now u can count number of tress in any rect. using simple math. with S. So, for each cell(i, j) check whether there are no tress in rect (i, j) _ (i + a — 1, j + b — 1). Inglesh is dead, sorry for that

→ Reply