Post Offices

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post Offices

Post by rushel »

can anybody please explain solution of this problem
http://acmicpc-live-archive.uva.es/nuev ... php?p=4273

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Post Offices

Post by mf »

Didn't you already ask that question on TC forums? What's not clear for you in rem's reply?

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Re: Post Offices

Post by rushel »

yes. oh how i am gonna decide where to place next post office if i know the result of dp[j-1].

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: Post Offices

Post by mf »

I imagine it with code like this:

Code: Select all

dp[j][0] = 0
for i = 1..n:
    dp[j][i] = infinity

for i = 1..n:
    let L[i] and R[i] be the first and last villages covered by a post office at i;
    dp[j][R[i]] = min(dp[j][R[i]], C[i] + (village L[i]-1 exists ? dp[j-1][L[i]-1] : 0))

for i = n-1..1:
    dp[j][i] = min(dp[j][i], dp[j][i+1])

for i = 1..n:
    dp[j][i] = min(dp[j][i], dp[j][i-1] + P[i])

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Re: Post Offices

Post by rushel »

thanks a lot

Post Reply

Return to “Algorithms”