乱搞系列之Google Code jam 四题

Minimum Scalar Product (2008 Round1A A)

这题想到贪心的方法不难, 看看样例就想到了. 如果要证明还是要思考一番. 证明的关键思想在于采用反证法证明简单情况, 用数学归纳推广到任意情况.

在所有能移动到第一行的备选行当中, 选择花费最低的. 然后用同样的方法处理第二行, 第三行, 第N行.

预处理 O(N^2), 选择并移动O(N^2). 所以最后的复杂度是O(N^2).

因为多组数据, 忘了memset数组, WA了好久.

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.

有趣的赌博问题,

也是一个搜索转为dp的题目.

不写了额看电影去了.