Hey, I was trying to solve this problem : http://www.usaco.org/index.php?page=viewproblem2&cpid=622

I came up with following approach which is kind of messy:

- States:

- Starting position (the first door that is open) (i)
- Ending position (the current last door that will be opened) (j)
- Count of doors already open before (k)

- Transition for all x < j: dp[i][j][k] = min(dp[i][x][k-1] + {something here}, dp[i][j][k-1])

{something here} = sum

for all y such that j-x+y >=0, x+(j-x+y)/2 ,

sum+= A[x+(j-x+y)/2]*(j-x+y+1)

for all y such that y < (j+(i+1))/2 , sum+=A[y]*(y-j);

for all y such that y > (j+(i+1))/2 and y < n , sum+=A[y]*(i+(n-y));

for all y such that y>=0 && y<i , sum+=A[y]*(y+1);

similar numbers will be subtracted from the solution.

What I am doing is, when we add new door/room, I take half the cows between last door and current door and add them to the solution.

Here is the actual solution of the problem : http://www.usaco.org/current/data/sol_cbarn2_gold_feb16.html

Can anyone explain me the following:

- If my approach correct ? (Forgetting the time constraints for now)
- How can this solution be obtained by optimising my solution ?
- How you came up to the solution ?

**Note: The point of posting my solution is that I am unable to understand the given solution. Now If anyone was willing to help they could suggest me how my solution/approach is wrong and how it can be optimised**

Auto comment: topic has been updated by DeathHunter (previous revision, new revision, compare).Auto comment: topic has been updated by DeathHunter (previous revision, new revision, compare).Auto comment: topic has been updated by DeathHunter (previous revision, new revision, compare).Auto comment: topic has been updated by DeathHunter (previous revision, new revision, compare).