Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

POJ 3260 The Fewest Coins ( Knapsack multiple & complete DP )

3260 -- The Fewest Coins n ≤ 100 types of currency exists, each value v[i] ≤ 120, and I have c[i] ≤ 100 of them. Answer the minimum sum of coins that I have to give and take, when I am to buy a product of T ≤ 10000 dollars. This is basical…

Lowest common ancestor

I have finally started to understand the LCA algorithm for transforming to RMQ. Here are the basic steps for static LCA queries: 1. DFS from any node as the root for the tree, making timestamps as it goes ( called the Euler's tour ). 3 bas…

Introduction to deque optimizations

A deque ( double ended queue ) is a data structure that supports push/ pop from both ends with constant time complexity. It can be used to optimize algorithms that deal with monotonous properties. The first time I saw this data structure, …

Introduction to stack optimizations

Stacks can be used to maintain for monotonous properties, can optimize for many problems, but only if you can discover the monotony in the problem. Here are some problems for exercise from the ant book. 3250 -- Bad Hair Day POJ 3250 Bad Ha…