spoj 10394. Buying Apples! | ABA12C

nice dp problem.
this is the simple dp that i came up first time but after watching the restriction on n, i modified it a bit and got 0.01 AC in python…


i --> weight of apples
j --> using first j items only
d[i][0] = inf
                --- dp[i][j - 1]                                       if weight[j] > i
dp[i][j] ---------- min(dp[i][j - 1], cost[j])                         if weight[j] == i
                --- min(dp[i - weight[j]][j] + cost[j], dp[i][j - 1])  if weight[j] < i


https://gist.github.com/8ec68d795798f33e5787

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s