acm规划(国外英语资料).docVIP

acm规划(国外英语资料) [transfer] ACM training programme,, 08, Saturday, 08 16:39[, ACM training programme] Some of the water problem on OJ (can be used to practice and increase self-confidence) (poj3299, poj2159, poj2739, poj1083, poj2262, poj1503, poj3006, poj2255, poj3094) Initial stage: I. Basic algorithm: (1) enumeration. (poj1753, poj2965) (2) greed (poj1328, poj2109, poj2586) (3) recursion and divide and conquer (4) recursion; (5) construction law. (poj3295) (6) simulation method. (poj1068, poj2632, poj1573, poj2993, poj2996) Two. Graph algorithm: (1) depth first traversal and breadth first traversal of Graphs (2) shortest path algorithm (Dijkstra, Bellman-Ford, Floyd, heap+dijkstra) (poj1860, poj3259, poj1062, poj2253, poj1125, poj2240) (3) minimum spanning tree algorithm (prim, Kruskal) (poj1789, poj2485, poj1258, poj3026) (4) topological sorting (poj1094) (5) the maximum matching of two graphs (Hungarian algorithm) (poj3041, poj3020) (6) maximum flow augmentation routing algorithm (KM algorithm). (poj1459, poj3436) Three. Data structure (1) string (poj1035, poj3080, poj1936) (2) sort (fast, return, side by side) (poj2388 (poj2299)) (3) the application of simple and check sets (4) hash table and two point search and other efficient search method (number of Hash, string of Hash) (poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503) (5) Huffman tree (poj3253) (6) pile (7) trie tree (static contribution, dynamic contribution) (poj2513) Four. Simple search (1) depth first search (poj2488, poj3083, poj3009, poj1321, poj2251) (2) breadth first search (poj3278, poj1426, poj3126, poj3087.poj3414) (3) simple search techniques and pruning (poj2531, poj1416, po Five. Dynamic programming (1) knapsack problem. (poj1837, poj1276) (2) the simple DP of the following table (refer to Lrjs book page149): 1.E[j]=opt{D+w (I, J)} (poj3267, poj1836, poj1260, poj2533) 2.E[i, j]=opt{D[i-1, j]+xi, D[i, j-1]+yj, D[i-1][j-1]+zij} (longest common subsequence) (poj3176, poj1080, poj1