Mission Possible
Time Limit: 36000/18000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 100 Accepted Submission(s): 16
Problem Description Mr. Frog loves playing video games. However, it seems that he does not have enough gift in this field, so he often gets stuck in some certain levels. Now this annoying situation comes to him again.
In this mission, Mr. Frog is asked to pass a
dangerous region which is currently under his enemies, control. Every second he is inside this region, his enemies would attack him with everything they have. Luckily, he is wearing a powersuit and still have time to enhance it.
powersuit has three main attributes： health point, velocity and recover speed. In the begin¬ning of this mission, the powersuit has H health points, and is able to move at no faster than Vm/s. Once the health point of powersuit is less than 0, the powersuit would be totally destroyed and Mr. Frog would immediately be killed. At the end of every second that the powersuit still works, the suit would repair itself and recover R health points.
After precise calculation, Mr. Frog has found that, to go through this area, he needs to run at least D meters distance, and every second his enemies, attack would cause A health point loss. Note that attacks take place all the time while the recover only happens at the end of every second, so you can consider that, in every whole second, the powersuit first loses A health points and then recovers R health points at the end of it, if it still works at that moment.
Mr. Frog could enhance his powersuit at any time he wants during the mission. At the beginning all three attributes of his powersuit equals to 0. He needs to pay
Input The first line contains only one integer T, which indicates the number of test cases. For each test case，there are five integers
Output For each test case，output one line “Case #x: Ans’’，where x is the case number (starting from 1) and Ans is the minimum cost required to finish the mission.
Sample Input
2
5 1 1 2 5
10 1 1 2 5
Sample Output
Case #1: 7
Case #2: 8
Hint
1 <= D,A <= 500000, 1 <= G1, G2, G3 <= 200
Source 2016CCPC东北地区大学生程序设计竞赛 - 重现赛
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 0, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
LL D, A, GH, GV, GR;
LL check(int V)
{
double T = 1.0 * D / V;
int RECT = T - 0.0001;
LL ret = 1e18;
{
LL R = 0;
LL H = max(T * A - RECT * R, (double)A) + 0.9999;
gmin(ret, H * GH + R * GR);
}
{
LL R = A;
LL H = max(T * A - RECT * R, (double)A) + 0.9999;
gmin(ret, H * GH + R * GR);
}
return ret;
}
int main()
{
scanf("%d", &casenum);
for (casei = 1; casei <= casenum; ++casei)
{
scanf("%lld%lld%lld%lld%lld", &D, &A, &GH, &GV, &GR);
LL ans = 1e18;
for (int l = 1; l <= D; ++l)
{
LL cost = check(l) + l * GV;
gmin(ans, cost);
}
printf("Case #%d: %lld\n", casei, ans);
}
return 0;
}
/*
【trick&&吐槽】
1，本题不满足三分性质，三分失败
2，attacks take place all the time while the recover only happens at the end of every second
所以我们要用double
3，其实只要考虑两种策略即可AC——
1，全部靠护甲不要恢复
2，全部靠恢复只要最基础的护甲
【题意】
我们一个人要穿过距离D，其每秒会受到A的攻击，这个攻击是每秒均摊的，也就是以浮点数的时刻计算
初始有
1，生命值H=0
2，速度V=0
3，每秒结束后的恢复力R=0
我们可以提升H,V,R，花费金钱数分别为GH,GV,GR，使得数值+1，V值的提升程度不能超过D
问你，如何花费，可以使得我们花费最小的金钱通过D的距离
D和A的范围都是[1,5e5]
GH,GV,GR的范围都是[1,200]
【类型】
线性规划 贪心 暴力
【分析】
首先，我们可以考虑枚举V∈[1,D]，然后得到T（T为double类型）
这时可以考虑再枚举R
我们有RECT*R+H>=T*A，所以可以贪心得到最小的H
然后用GV*V+GH*H+GR*R更新答案即可。
只不过这里的的复杂度有些大
我们考虑不枚举R，而是贪心发现H=T*A-RECT*R
我们希望（T*A-RECT*R）*GH + GR*R尽可能小
即要使得T*A*GH + GR*R - RECT*GH*R尽可能小
即要使得（T*A*GH）+（GR-RECT*GH）*R尽可能小
GR-RECT*GH是可能为正可以为负的，所以R在其最小取值或最大取值时最优。
但是有一点要注意，我们需要时刻维护使得T*A-RECT*R >= H
但是这并不影响我们的决策点
【时间复杂度&&优化】
O（D）
*/