Dynamic Programming Exercises Beginner 归档题解(3)
2016-02-13
归档地址 最后五题了。
题目 UVa 473 - Raucous Rockers 简单的 01 背包,直接给 DP: d p [ i ] [ j ] [ k ] dp[i][j][k] d p [ i ] [ j ] [ k ] 决策前 i i i 首......
Dynamic Programming Exercises Beginner 归档题解(2)
2016-02-13
归档地址 再来10题!
题目 UVa 10817 - Headmaster's Headache 由于每个申请者可选可不选,所以就像一个 01 背包一样。用上一篇定状态的方法,对后面决策的影响就只有现在剩余哪些课没人教。所以定义状态: d p [ i ] [ s ] dp[i][s] d p [ i ] [ s ]......
UVa 10453 - Make Palindrome
2016-02-10
题目地址
描述 给定一个长度为 n ( n ≤ 1 0 0 0 ) n(n\le 1000) n ( n ≤ 1 0 0 0 ) 的字符串,你需要在任意位置添加尽量少的字符,使新串是回文串。输出最少添加的字符个数以及新串。
样例输入 abcd
aaaa
abc
aab
abababaababab......
UVa 1351 - String Compression
2016-02-08
题目地址
描述 有一个长度为 n ( n ≤ 2 0 0 ) n(n\le200) n ( n ≤ 2 0 0 ) 的字符串,我们现在要尽可能的压缩这个字符串,使这个字符串的长度尽可能的短。如果一个子串 S S S 连续重复 k k ......
UVa 1452 - Jump
2016-02-07
题目地址
描述 有 n ( n ≤ 5 0 0 0 0 0 ) n(n\le500000) n ( n ≤ 5 0 0 0 0 0 ) 个人顺时针排成一个圆圈,依次顺时针标号 1 − n 1 - n 1 − n 。现在从 1 1 ......
Dynamic Programming Exercises Beginner 归档题解(1)
2016-02-05
归档地址
搞这个归档模块,其实是我想写题解却懒得搞题意和输入输出之类的,这样可以方便我写分析。所以题意大家就看刘汝佳的训练指南 P93 吧。再一个是我 DP 弱的要死,赶紧总结一下方法。。。
本题解是边做题边写的,所以比较仓促,有问题欢迎留言,或是发我邮件 sengxian at live.com
题目 UVa 11584 - Partitioning by P......
UVa 1394 - And Then There Was One
2016-02-04
题目地址
描述 有 n ( n ≤ 1 0 0 0 0 ) n(n\le10000) n ( n ≤ 1 0 0 0 0 ) 个人顺时针排成一个圆圈,依次顺时针标号 1 − n 1 - n 1 − n 。一开始标号为 m m ......