首页 > 其他分享 >E. FTL

E. FTL

时间:2022-10-25 17:47:40浏览次数:70  
标签:enemy 激光 FTL leq 射击 times spaceship

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

标签:enemy,激光,FTL,leq,射击,times,spaceship
From: https://www.cnblogs.com/onlyblues/p/16825595.html

相关文章

  • 1743E - FTL
    1743E-FTLAtanytime,wehavethreepossiblechoices:waitandshootthefirstlaser,thesecondlaserandbothlasers.Sometimesitmakessensetowaitto......
  • CF1743 E - FTL(线性DP)
    E-FTL(线性DP)题意​ 现在你有两支激光枪,枪A伤害为\(p_1\),冷却时间为\(t_2\);枪B伤害为\(p_2\),冷却时间为\(t_2\)。敌人的护甲为s,可以抵消每一次攻击中的s点伤害。请问最......
  • Educational Codeforces Round 137 (Rated for Div. 2) - E. FTL
    DPProblem-E-Codeforces题意有个BOSS有\(H\;(1<=H<=5000)\)血量,\(s\)点防御有两种武器可用攻击BOSS,伤害分别为\(p_1,p_2\;(s<min(p_1,p_2)<=5000)\),冷却......
  • SwiftLint - iOS 应用程序代码检查
    SwiftLint-iOS应用程序代码检查用风格编写干净的代码SwiftLint是一个快速的代码风格分析工具,有助于标记风格错误****在代码中。SwiftLint强制执行Swift社区普......