Description 有一个大小为 的大方格，初始小人在位置 。记小人的位置为 ,每秒小人都能够移动至 的范围内。 给不定数个苹果，对苹果 , 在 时刻出现在, 下落速度为 , 价值为 。 求小人通过最优移动能够获得的最大价值和 打印小人每秒的移动策略 Solution 考虑 不难想到DP数组 的状态设置为小人在第 秒，位于位置 时获得的最大价值和。 是小人在第 秒，位于位置 时能够获得的价值和 由于起始位置固定，不妨倒过来DP。 答案就是 求DP的路径只需要记录是怎么转移的即可。 code #include <bits/stdc++.h> #d...

Description 有 朵花, 个花瓶, 每朵花插在不同的花瓶都会产生不同的价值(正负数都有)。 你要按顺序依次将 朵花插入 个花瓶中，并保证第 朵花插入的位置 满足 求满足条件的插完 朵花的价值和的最大值。 打印价值和最大时从小到大插花的花瓶位置 Solution 对于问题一： 考虑将第 朵花插入第 位时代价和的最大值。记为 。 发现状态只跟 和 有关 但是这样暴力转移的复杂度高，需要优化。 不妨将 记为第 朵花插在前 个花瓶处代价的最大值。 此时的状态就只跟 和 相关联 所以我们就得到了状态转移方程 注意当 时我们要强制转移，因为此时第 朵花必须插在...

Description 有 个大小为 的连通块，规定合并连通块的代价为 连通块的大小之差，求将这 个联通块合并为 个连通块所需的最小代价。 Solution 思路: 显然，当连通块大小相等时合并连通块的代价为 0。 所以我们可以通过分治的思路去解决合并大小为 (n/2) 和 (n - n/2) 最小代价。 对于每个大小为 k 的连通块，只有当 k 为奇数时才有可能产生贡献 当 k 为奇数时，产生的贡献为合并 (k/2 + 1) 的代价 + 合并 (k / 2)的代价 + 1[(k / 2 + 1) - (k / 2)] 所以我们可以通过递归解决这个问题，递归边界是 k == 1。 T...