Help required in Simple DP problem

general
,
1

Problem Link http://www.codechef.com/problems/COUPON

Can anyone help me with this solution http://www.codechef.com/viewsolution/6986215
First tell what should I do to get 60 points and then 100 points.

I have got 20 points in this solution. I thought I would get TLE in rest of subtask but its giving WA.
Can anyone tell me in which case I am getting WA

2

Your dp equation needs to be modified. You wrote dp[j][k] = dp[j - 1][k] + min(disc, min). I assume dp[j][k] denotes the total cost of j items with last item bought in the kth house. Then min(disc, min) is wrong. It should be only disc. And it it not necessary that he always gets a discount. It is also possible that dp[j][k] = dp[j - 1][h] + price[j][k] where h is anything from 1 to m.

So your final dp equation should be

dp[j][k] = min(dp[j - 1][k] + disc, val + price[j][k])
where val = min of all (dp[j - 1][h]) for h in range (1, m)

1 Like