动态规划习题(1)
入门习题 (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 |
中级习题 (Exercises:Intermediate)
LA4945 | Free Goodies | 也可以贪心,时间效率更高 |
LA4327 | Parade | 模型不难想,但需要优化 |
LA4015 | Cave | 树的动态规划 |
LA4490 | Help Bubu | |
UVa11600 | Masud Rana | 注意状态表示 |
LA4987 | Evacuation Plan | |
LA4613 | Mountain Road | |
LA4614 | Moving to Nuremberg | |
LA4050 | Hanoi Towers | |
LA3305 | Tour | 经典问题 |
LA3412 | Pesky Heroes | 树的动态规划(题目不太好理解) |
LA3679 | Pitcher Rotation | 需要一点优化(精简状态) |
LA3605 | Roommate | |
LA3608 | Period | |
LA3610 | Log Jumping | 可以转化为经典问题 |
LA2221 | Frontier | 涉及到几何(见第四章)的动态规划 |
LA3132 | Minimax Triangulation | |
LA3710 | Interconnect | 注意状态表示 |
LA5088 | Alice and Bob's Trip | 树上的动态规划 |
LA3782 | Bigger is Better | 有多种方法。可以不用高精度 |
(extra)UVa10003 | Cutting Sticks | 经典的动态规划题目。可以用四边形不等式优化 |
(extra)UVa10239 | The Book-shelver's Problem | |
(extra)UVa10271 | Chopsticks | |
(extra)UVa10304 | Optimal Binary Search Tree | |
(extra)UVa10599 | Robots(II) | |
(extra)UVa10604 | Chemical Reaction | |
(extra)UVa10618 | Tango Tango Insurrection | |
(extra)UVa10641 | Barisal Stadium | |
(extra)UVa10671 | Grid Speed | |
(extra)UVa10688 | The Poor Giant | |
(extra)UVa11263 | Nested Rectangles | |
(extra)UVa11400 | Lighting System Design | |
(extra)UVa11578 | Situp Benches | |
(extra)UVa11691 | Allergy Test | |
(extra)UVa11766 | Racing Car Computer | |
(extra)UVa12002 | Happy Birthday | |
(extra)UVa10723 | Cyborg Genes | 推荐 |
(extra)UVa10934 | Dropping water | 推荐 |
(extra)UVa10981 | String Morphing | 推荐 |
(extra)UVa11307 | Alternative Arborescene | 推荐 |
(extra)UVa11456 | Trainsorting | |
(extra)UVa11782 | Optimal Cut | |
(extra)LA2096 | Taekwondo | |
(extra)LA2151 | Telescope |
提高习题 (Exercises: Advanced)
LA4394 | String Painter | 序列的动态规划,有一定难度 |
LA4593 | Exclusive Access 2 | |
LA4048 | Fund Management | 注意状态表示 |
LA4625 | Garlands | |
LA3683 | A Scheduling Problem | 树的动态规划 |
LA3637 | The Bookcase | 不太容易想到,且需要优化 |
LA5717 | Peach Blossom Spring | 一类经典题目(最早出现在NWERC2006,但本题数据更强) |
LA3623 | The Best Name for Your Baby | 有难度的动态规划;注意计算顺序 |
LA4002 | The Ultimate Password | 有难度的动态规划;注意计算顺序 |
LA2178 | The Minimum Number of Rooks | 有难度的动态规划 |
LA2923 | Bundling | |
LA2930 | Minimizing Maximizer | 01 原则;数据结构优化动态规划 |
LA3181 | Fixing the Great Wall | |
LA4290 | Easy Climb | 需要优化 |
UVa10559 | Blocks | 重点是设计状态及其转移 |
LA4031 | Integer Transmission | 需要认真思考。可以做到O(n^2)时间。 |
UVa11521 | Compressor | 需要认真思考。很容易写错。 |
(extra)UVa10949 | Kids in a Grid | |
(extra)UVa11193 | Infinix | |
(extra)UVa11194 | Stone Grid | |
(extra)UVa11810 | Gentle ping, to the old King | |
(extra)UVa11171 | SMS | |
(extra)UVa11435 | Network EXTREME!!! | 推荐 |
(extra)UVa11502 | Rocket Stages | |
(extra)UVa11750 | Red-Blue Tree | 推荐 |
(extra)UVa11803 | The Great Merge |