uva 216 - Getting in Line

  1 /*
  2  Problem link
  3  Type: DP - TSP
  4  Algorithm: Brute force, back-tracking
  5  */

uva 571 - Jugs

  1  /*
  2  Problem link
  3  Type: Graph - DP
  4  Algorithm: BFS
  5  */

uva 11517 - Exact Change

/*
Problem link
Type: DP - Coin change
Algorithm:
*/

uva 10313 - Pay the Price

 1 /*
 2  Problem link
 3  Type: DP - coin change
 4  Algorithm:

uva 11137 - Ingenuous Cubrency

 1 /*
 2  Problem link
 3  Type: DP
 4  Algorithm: Coin change
 5  */

uva 10306 - e-Coins

 1  /*
 2  Problem link
 3  Type: DP - Coins change
 4  Algorithm:
 5      First I use the function getP to search for a list of possible points with
 6       length = s from the origin and have possitive coordinates.
 7      Use the coins change algorithm (uva 166) with a few changes to find the
 8       minimum step to each point i got. Get the minimum for each point result.
 9  */

uva 357 - Let Me Count The Ways

/*

Problem link

Type: DP - Coin change

*/

uva 10819 - Trouble of 13-Dots

 1 /*
 2  Problem link
 3  Type: DP, knapsack(0/1)
 4  */

uva 166 - Making Change

  1 /*
  2  Problem link
  3  Type: DP
  4  Algorithm:

uva 147 - Dollars

 1 /*
 2  Problem link
 3  Type: DP
 4  Algorithm:

uva 10616 - Divisible Group Sums

/*
Problem link
Type: DP, Mathematics
Algorithm:
 Let f(i,j,k) is the number of ways to choose i elements from a[1..j] so that
 their sum divides d gives the remainder of k. 

uva 473 - Raucous Rockers

/*
Problem link
Type: DP
Algorithm:
 Let f(i,j,k) be the largest amount of songs from 1 to k can be written into 
 the disks from 1 to i with disk i having space j

The Fibonacci Numbers

• The rabbits growth problem:

Fibonacci's book Liber Abaci written in 1202 concerned about the growth of the number of rabbits in a certain area. The problem is: A young pair of rabbits, one of each sex, is placed on an island. Assuming that rabbits do not breed until they are two months old and after they are two months old, each pair of rabbits produces another pair each month, how many pairs are there after n months?

Let f(n) be the number of rabbits after n months. We have f(1) = 1 because only the original pair is on the island after one month. As this pair does not breed during the second month, f(2) = 1. To find the number of pairs after n months, add the number on the island the previous month, f(n-1), to the number of newborn pairs, which equals to f(n-2), because each newborn pair comes from a pair at least two months old. This leads to the following definition.

• Definition: 

The Fibonacci sequence is defined recursively by f(1) = 1, f(2) = 1, and f(n) = f(n-1) + f(n-2) for n>=3. The terms of this sequence are called the Fibonacci Numbers

uva 1213 - Sum of Different Primes

/*

Problem link
Type: DP, Prime
Algorithm:
 Let f(i,j,k) is the number of way to split number i into j prime numbers 
 using the first k prime numbers
 
 If we decide to choose the kth prime in the sum, then the number of ways
 is f(i-Prime[k],j-1,k-1), that is, the number of way to split number
 i-Prime[k] into j-1 prime numbers (and the kth prime number) using 
 the first k-1 prime numbers (cannot choose Prime[k] again)

uva 10664 - Luggage

/*

Problem link

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
//-----------------------------
void readfile();
bool solve();

uva 10667 - Largest Block

/*
Problem link
Type: DP, data structure
Algorithm: I use the stack in the problem, with this I can solve it in O(n^2)
 Let h[i][j] be the height of the consecutive comlumn of 0 at (i,j)
 Let l[i][j] is the index left most element of (i,j) that from h[i][l[i][j]] to h[i][j]
  is all >= h[i][j]
 Let r[i][j] is the index right most element of (i,j) that from h[i][j] to h[i][r[i][j]]
  is all >= h[i][j]
 Find max of (j-l[i][j]+r[i][j]-j+1)*h[i][j] for all i,j
 l and r are calculated in O(n^2) by using the stack
*/

uva 787 - Maximum Sub-sequence Product

/*

Problem link
Type: DP, BigNum
Algorithm:
 Just go for an O(n^2) to calculate each product from i to j.
 The bignum is a bit tricky, I build a class for BigNum here so it can be processed easily.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;

uva 10534 - Wavio Sequence

/*

Problem link
Type: DP, LIS, LDS
Algorithm: 
 - Find the LIS and save the LIS til index i in array d1.
 - Find the LDS by do the LIS backward and save the LDS till index i in array d2.
 - For each element, consider it as the top element of the waivo.
*/

uva 10131 - Is Bigger Smarter?

/*

Problem link
- This problem is a good example of both LIS and LCS. I solved this problem
using the LCS DP (Longest Common sub-Sequence).
** Algorithm:
- The algorithm for the LCS is simple. 
- First we sort the list of the cows in increasing 
order of weight, save their corresponding ID in array l1.
- Second, sort the list of the cows in decreasing 
order of smart, save their corresponding ID in array l2.
- Find the LCS of l1 and l2.

uva 437 - The Tower of Babylon

/*

Problem link

This problem can be attacked in many solution. I choose the DP solution.

It is a bit similar to the LIS.