Minimum Scalar Product (2008 Round1A A)
这题想到贪心的方法不难, 看看样例就想到了. 如果要证明还是要思考一番. 证明的关键思想在于采用反证法证明简单情况, 用数学归纳推广到任意情况.
Crazy Rows (2009 Round2 A)
在所有能移动到第一行的备选行当中, 选择花费最低的. 然后用同样的方法处理第二行, 第三行, 第N行.
预处理 O(N^2), 选择并移动O(N^2). 所以最后的复杂度是O(N^2).
因为多组数据, 忘了memset数组, WA了好久.
Bribe the Prisoners (2009 Round 1C C)
P个牢房释放Q个人的问题
首先想到的是递归解决问题, 比如dfs(a, b), 枚举i, a < i < b, 然后 dfs(a, b) = dfs(a, i) + dfs(i, b) + cost[i] 之类的. 考虑到这样可能会有重复计算的地方, 那么可以用记忆化搜索.
书上用的是动态规划. 我觉得把思路从递归转化到动态规划是比较好玩的事情. 有些递归是不那么好转的, 比如在解答树上的叶子的深度深浅不一的时候, 或者解答树的枝叶长得比较凌乱的时候- -||
所以我觉得考虑递归边界是否整齐是一个好的判断是否能转化为dp的一个好方法. 而对dp的状态进行定义是一个关键步骤, 决定了递归边界是如何界定的.
书上的状态定义如下
dp[i][j] : 将从A[i]号到B[i]号的囚犯(不含这两个)的连续部分的所有囚犯都释放的时候, 所需要的最少金币总数.
显然"叶子节点"是 dp[i][i+1] = 0.
目标是要求出dp[0][Q+1].
从叶子节点向上延伸一层的时候, 就是状态转移方程要写出的意思:
dp[i][j] = A[j] � A[i] � 2 + min{dp[i][k], dp[k][j]} , i < k < j.
What are Birds? (APAC Semifinal 2008 C)
有趣的赌博问题,
也是一个搜索转为dp的题目.
不写了额看电影去了.
Read full article from 乱搞系列之Google Code jam 四题 - Jecvay Notes
No comments:
Post a Comment