USACO problem : Circular Barn Revisted
Difference between en3 and en4, changed 401 character(s)
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: ↵
1. Starting position (the first door that is open) (i)↵
2. Ending position (the current last door that will be opened) (j)↵
3. 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↵

1. 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)↵

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

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

4. 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:↵

1. If my approach correct ? (Forgetting the time constraints for now)↵
2. How can this solution be obtained by optimising my solution ?↵
3. 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**↵

**PS: Its wierd how this community gives 2000+ upvotes to a post regarding sexism but at the same time if can not help but also discourages posts regarding helping with a question**

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English DeathHunter 2021-02-27 17:19:09 181
en4 English DeathHunter 2021-02-27 17:09:41 401
en3 English DeathHunter 2021-02-27 16:58:36 4
en2 English DeathHunter 2021-02-27 16:46:39 6
en1 English DeathHunter 2021-02-27 08:42:07 1307 Initial revision (published)