[to record the solution for my own record for easy understanding]
Problem statement: http://usaco.org/index.php?page=viewproblem2&cpid=1068
dp[i, j, k] where
i-th barn, where the corresponding cows that fits is match[i]
out of match[i] cows, j of them are assigned to barn i+1 ... N
and flag = 0 means no mis-match cows / all cows are in barns, 1 = allow some cows to left behind
so, each time we add a new barn (barn and cow are sorted low to high), we have an additional match[i] ... match[i-1] cow to assign. Let's take j from dp[i-1] and k from those now cows
dp[i, j+k, f] += dp[i, j, f] * (probability of picking k out of match[i] ... match[i-1], which is a simple c(n,m) )
note that barn i is the largest, so it must be occupied unless all cows are assigned (i.e. f = 0). So, in above case
if we pick j from dp[i-1], and one of them landed at barn i, it is good, but the number of cow after barn i+1 is actually j+k-1
if it does not land at barn i, for the k cow we picked, one of them must be used for barn i. And again then, the correct index should be j+k-1.
So, after the above dp, before we finish barn i, we need to do j+1 -> j index shift for f = 1. Note that we can pick any of (j+1) cow to fit at barn i, so times (j+1).
if f=0, all the cows are assigned so that we can leave barn i open (not used). So, we need the original count (not assign to barn i) and add the j+1 -> j shift
.
Comments (0)
