[置顶] 刘汝佳《训练指南》动态规划::Beginner （25题）解题报告汇总

本文出自   http://blog.****.net/shuangde800

刘汝佳《算法竞赛入门经典-训练指南》的动态规划部分的习题Beginner  打开

这个专题一共有25题，刷完后对dp的感觉提升了不少。

现把解题报告整理了一下，希望对大家能有帮助。

入门习题 （Exercises: Beginner）

UVa11584	Partitioning by Palindromes	入门题目
LA4256	Salesman	入门题目
UVa10534	Wavio Sequence	可以转化为经典问题，时间O(nlogn)
UVa11552	Fewest Flops	序列划分模型；状态设计
UVa11404	Palindromic Subsequence	可以转化为LCS
LA4731	Cellular Network	需要一点概率知识和推理
UVa11795	Mega Man's Missions	基础的集合动态规划
LA4727	Jump	Joseph问题的变形
LA3530	Martian Mining	模型简单，但需要减少重复计算
UVa10564	Paths through the Hourglass	类似01 背包问题
UVa10817	Headmaster's Headache	集合动态规划
LA2038	Strategic Game	树上动态规划（基础题）
LA3363	String Compression	字符串动态规划
LA2031	Dance Dance Revolution	以跳舞机为背景的题目
LA4643	Twenty Questions	有趣的问题；比较基础的动态规划
(extra)UVa10163	Storage Keepers
(extra)UVa10453	Make Palindrome
*(extra)UVa10254	The Priest Mathematician
**(extra)UVa437	The Tower of Babylon
**(extra)UVa442	Matrix Chain Multiplication	最优矩阵乘法
**(extra)UVa473	Raucous Rockers	可以优化
**(extra)UVa590	Always on the Run
**(extra)UVa607	Scheduling Lectures
**(extra)UVa662	Fast Food	可以优化
**(extra)UVa672	Gangsters

11584 - Partitioning by Palindromes   题解

1424 - Salesmen 题解

10534 - Wavio Sequence  题解

11552 - Fewest Flops  题解

11404 - Palindromic Subsequence    题解

1456 - Cellular Network    题解

11795 - Mega Man's Mission  题解

1452 - Jump  题解

1366 - Martian Mining题解

10564 - Paths through the Hourglass  题解

10817 - Headmaster's Headache  题解

1292 - Strategic game  题解

1351 - String Compression  题解

1291 - Dance Dance Revolution     题解

1252 - Twenty Questions  题解

10163 - Storage Keepers  题解

10453 - Make Palindrome    题解

10254 - The Priest Mathematician  题解

437 - The Tower of Babylon   题解

442 - Matrix Chain Multiplication   题解

473 - Raucous Rockers  题解

590 - Always on the run  题解

607 - Scheduling Lectures 题解

662 - Fast Food  题解

672 - Gangsters  题解