Hmm, soal ini bagus banget. Memberikan pengetahuan baru tentang satu style baru dalam DP, yakni DP in graph (especially tree dalam soal ini). Intinya dalam solusi soal ini, kita harus melakukan traversing dalam sebuah tree, lalu dari setiap nodenya kita melakukan DP 3 dimensi. Traversing yang dimaksud dapat dilakukan secara bottom-up maupun top-down. Buat yang mau liat soalnya silakan liat di situs resminya IOI 2005, kalau mau solusinya gw anjurkan untuk liat nih source -> riv_sol.doc . Itu solusi yang gw dapet dari seorang pelatih Tim Olimpiade Cina, gw bilang tuh solusi bagus, karena dia simple (pake top-down memoization untuk traversingnya) dan cara dia membuat representasi treenya gaya banget. Well, buka, baca, pelajari, dan terkagumlah…

Thursday, May 31st, 2007 @ 2:28 am Computing
RSS 2.0 Trackback