E. FTL
Monocarp is playing a video game. In the game, he controls a spaceship and has to destroy an enemy spaceship.
Monocarp has two lasers installed on his spaceship. Both lasers $1$ and $2$ have two values:
$p_i$ — the power of the laser;
$t_i$ — the reload time of the laser.
When a laser is fully charged, Monocarp can either shoot it or wait for the other laser to charge and shoot both of them at the same time.
An enemy spaceship has $h$ durability and $s$ shield capacity. When Monocarp shoots an enemy spaceship, it receives $(P−s)$ damage (i. e. $(P−s)$ gets subtracted from its durability), where $P$ is the total power of the lasers that Monocarp shoots (i. e. $p_i$ if he only shoots laser $i$ and $p_1+p_2$ if he shoots both lasers at the same time). An enemy spaceship is considered destroyed when its durability becomes $0$ or lower.
Initially, both lasers are zero charged.
What’s the lowest amount of time it can take Monocarp to destroy an enemy spaceship?
Input
The first line contains two integers $p_1$ and $t_1$ $(2 \leq p_1 \leq 5000; 1 \leq t_1 \leq {10}^{12})$ — the power and the reload time of the first laser.
The second line contains two integers $p_2$ and $t_2$ $(2 \leq p_2 \leq 5000; 1 \leq t_2 \leq {10}^{12})$ — the power and the reload time of the second laser.
The third line contains two integers $h$ and $s$ $(1 \leq h \leq 5000; 1 \leq s < \min(p_1,p_2))$ — the durability and the shield capacity of an enemy spaceship. Note that the last constraint implies that Monocarp will always be able to destroy an enemy spaceship.
Output
Print a single integer — the lowest amount of time it can take Monocarp to destroy an enemy spaceship.
Examples
input
5 10 4 9 16 1
output
20
input
10 1 5000 100000 25 9
output
25
解题思路
当时比赛时以为这题是贪心，后面看题解才知道是动态规划。看题解的时候也完全看不懂别人在写什么。今天再看了看大概明白了怎么一回事，写下来记录一下。
首先为什么可以用动态规划来做，是因为方案由激光射击的不同顺序组成，因此对于同一个的伤害，就有多种不同的激光射击顺序（对应的有不同的消耗时间），因此可以根据造成的伤害来定义状态，然后根据最后一次射击的激光来划分集合（单独射击激光$1$、单独射击激光$2$，两个激光同时射击）。
定义状态$f(i)$，表示所有造成至少$i$点伤害的激光射击方案，属性是消耗时间的最小值。如果最后一次是单个激光的射击，那么状态转移方程就比较好写。
如果最后一次射击是激光$1$，那么$f(i) = \min\{ {f(i), \,\, f(\max\{ {0, i – p_1 + s} \}) + t_1} \}$。
同理如果是最后一次射击是激光$2$，那么$f(i) = \min\{ {f(i), \,\, f(\max\{ {0, i – p_2 + s} \}) + t_2} \}$.
如果最后一次是同时射击，状态就不容易转移了，因为我们不知道加多少时间，即$f(i – p_1 – p_2 + s) + ?$。为了能求出这种状态的转移方程，我们需要明确的时间，假设同时射击前（包括）激光$1$一共射击了$j$次，那么在激光$1$射击了$j$次这段时间内（$j \times t_1$），激光$1$造成的伤害为$(j – 1) \times (p_1 – s)$，而激光$2$最多能造成的伤害为$\left\lfloor {(j \times t_1 – t_2) / t_2} \right\rfloor \times (p_2 – s)$，因此总的伤害就为$t = (j – 1) \times (p_1 – s) + \left\lfloor {(j \times t_1 – t_2) / t_2} \right\rfloor \times (p_2 – s) + p_1 + p_2 – s$，对应状态转方程就是$f(i) = \min\{ {f(i), \,\, f(\max\{ {0, i – t} \}) + j \times t_1} \}$。因此我们从$1$开始枚举$j$，由于一次攻击至少一点伤害，因此可以枚举到$i$。
同理也要枚举激光$2$射击的次数$j$，总伤害就是$t = (j – 1) \times (p_2 – s) + \left\lfloor {(j \times t_2 – t_1) / t_1} \right\rfloor \times (p_1 – s) + p_1 + p_2 – s$，状态转方程为$f(i) = \min\{ {f(i), \,\, f(\max\{ {0, i – t} \}) + j \times t_2} \}$。
AC代码如下，时间复杂度为$O(n^2)$：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 const int N = 5010; 7 8 LL f[N]; 9 10 int main() { 11 LL p1, t1, p2, t2, n, s; 12 cin >> p1 >> t1 >> p2 >> t2 >> n >> s; 13 14 memset(f, 0x3f, sizeof(f)); 15 f[0] = 0; 16 for (int i = 1; i <= n; i++) { 17 f[i] = min(f[max(0ll, i - p1 + s)] + t1, f[max(0ll, i - p2 + s)] + t2); // 最后一次是单独射击的情况 18 // 最后一次是同时射击的情况 19 for (int j = 1; j <= i; j++) { 20 if (j * t1 < t2) continue; // 因为同时射击，因此激光2至少要射击一次 21 LL t = (j - 1) * (p1 - s) + (j * t1 - t2) / t2 * (p2 - s) + p1 + p2 - s; 22 f[i] = min(f[i], f[max(0ll, i - t)] + j * t1); 23 } 24 for (int j = 1; j <= i; j++) { 25 if (j * t2 < t1) continue; // 因为同时射击，因此激光1至少要射击一次 26 LL t = (j - 1) * (p2 - s) + (j * t2 - t1) / t1 * (p1 - s) + p1 + p2 - s; 27 f[i] = min(f[i], f[max(0ll, i - t)] + j * t2); 28 } 29 } 30 31 cout << f[n]; 32 33 return 0; 34 }
参考资料
Educational Codeforces Round 137 (Rated for Div. 2) 补D、E：http://www.wtld.cn/a/72097.html
原文地址：http://www.cnblogs.com/onlyblues/p/16825595.html
