魔力屏障 (magic) 题解

魔力屏障 (magic)

【问题描述】

小 Z 生活在神奇的魔法大陆上。今天他的魔法老师给了它这样一个法阵作为它 的期末考试题目： 法阵由从左至右 n 道魔力屏障组成，每道屏障有一个临界值 a，如果它承受攻 击的魔力值 ≥ a，屏障将会破碎，它所承受的魔力攻击将在魔力值减半后（向下取 整）继续向右移动，否则该攻击会被该屏障完全拦截，停留在屏障前，屏障的临界 值不会减少。当两次攻击相遇时，两次攻击会叠加形成新的攻击，新的攻击的魔力 值为两次攻击魔力值之和，新的攻击会继续向右移动。小 Z 可以在法阵中任意一个 位置释放任意大小魔力值的攻击，攻击会向右移动直到遇到一个还未被摧毁的屏障 或离开法阵。 对于所有 1 ≤ i ≤ n ，小 Z 希望用最小的法力值使得第 1 ～ i 道屏障全部破碎。

【输入格式】

第一个一个正整数 n 表示屏障的数量。 第二行 n 个正整数，第 i 个数为第 i 道屏障的临界值。

【输出格式】

一行 n 个数，第 i 个表示使第 1 ～ i 道屏障全部破碎的最小法力值。两个数之 间用一个空格隔开。

【样例 1 输入】

5 10 3 3 8 4

【样例 1 输出】

10 10 11 17 17

【样例 1 解释】

对于 i = 1 ～ 3，直接从左到右释放攻击使得屏障恰好破碎，例如 i = 3 时依次 在屏障 1 ～ 3 上释放魔力值为 10, 0, 1 的攻击。对于 i = 4, 5 的方案，先在第 3 道屏 障上释放魔力为 2 的攻击，再在第 2 道屏障上释放魔力为 3 的攻击，此时屏障 2, 3 都已被破碎，屏障 4 上留有魔力值 1 的攻击。此时再在第 1 道屏障上释放魔力为 10 的攻击，在第 4 道屏障上释放魔力为 2 的攻击，第 4, 5 道屏障都被击碎。

【样例 2】

见选手目录下的 magic2.in 与 magic2.ans。 该样例与子任务 2 满足同样的约束条件。

【样例 3】

见选手目录下的 magic3.in 与 magic3.ans。 该样例与子任务 3 满足同样的约束条件。

【样例 4】

见选手目录下的 magic4.in 与 magic4.ans。 该样例与子任务 4 满足同样的约束条件。

【数据规模与约定】

本题开启子任务测试。对于所有数据满足 1 ≤ n ≤ 70, 1 ≤ ai ≤ 150。 子任务编号 分值 n ≤ ai ≤ 子任务依赖 1 30 10 5 无 2 20 20 10 1 3 20 70 2 无 4 30 70 150 2,3

总结：

最开始我想就是区间DP，状态也是 f[i][j][k] 表示打完 i-j 还剩 k 的能量，

但我最开始想法是用前部分的剩余能量的一部分攻击后半部分的能量，但这其实不好处理前半部分剩余能量的一部分。

正解是用前半部分的剩余能量全部留下，和后半部分的一起留下成为一坨新的能量一起留给后面。

当然也有前半部分的剩余能量攻击后半部分的情况，但攻击只会攻击一个屏障，可以特殊判定一下 [i-j] 被分割为 [i-j-1] 和 [j] 两个部分，前部分剩余能量攻击 j ,仔细想想这样可以包含完全部情况