Educational Codeforces Round 137 (Rated for Div. 2)

DP

Problem - E - Codeforces

题意

有个 BOSS 有 \(H\;(1<=H<=5000)\) 血量，\(s\) 点防御

有两种武器可用攻击 BOSS，伤害分别为 \(p_1,p_2\;(s<min(p_1,p_2)<=5000)\), 冷却时间分别为 \(t_1,t_2\;(1<=t_1,t_2<=10^{12})\)

每一时刻如果 cd 好了可以选择攻击，造成 \(p_i-s\) 点伤害；如果两个武器一起攻击可以造成 \(p_1+p_2-s\) 点伤害

0 时刻两个武器都刚进入 cd，求将 BOSS 消灭的最短时间

思路

可以选择攻击的时刻一定是 \(p_1\) 或 \(p_2\) 的倍数，并且每次至少造成 1 点伤害，因此最多有 \(H\) 个需要抉择的时刻 \(T_i\)
当某时刻两个武器同时发射时，之后的操作就成了一个子问题
可以设 \(f[h]\) 为两个武器都刚进入 cd，打掉 h 血的最短时间，枚举 \(T_i\), 作为第一次刻意等待令两个武器同时发射的时刻，求出前 \(T_i\) 时间正常操作（即 cd 好了就放）造成的伤害 \(tot\), \(f[h]=min(f[h],f[h-tot]+T_i)\)

代码

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

typedef pair<int, int> PII;

const int N = 5e3 + 10;

int p[3], H, s;

ll t[3], cnt[3];

ll f[N];

vector<ll> vt;

ll lcm(__int128 a, __int128 b)

{

	__int128 t = a / __gcd(a, b) * b;

	if (t >= (__int128)2e18)

		t = 2e18;

	return t;

}

void presolve()

{

	if (t[1] > t[2])

	{

		swap(t[1], t[2]);

		swap(p[1], p[2]);

	}

	p[0] = p[1] + p[2] - s;

	p[1] -= s, p[2] -= s;

	t[0] = lcm(t[1], t[2]);

	for (int i = 1; i * p[1] <= H; i++)

		vt.push_back(i * t[1]);

	for (int i = 1; i * p[2] <= H; i++)

		vt.push_back(i * t[2]);

	sort(vt.begin(), vt.end());

	vt.erase(unique(vt.begin(), vt.end()), vt.end());

}

void solve()

{

	memset(f, 0x3f, sizeof f);

	f[0] = 0;

	for (int h = 1; h <= p[1]; h++)

		f[h] = t[1];

	for (int h = p[1] + 1; h <= H; h++)

	{

		for (auto T : vt)

		{

			if (T % t[0] == 0)

			{

				cnt[0] = T / t[0];

				cnt[1] = T / t[1] - cnt[0];

				cnt[2] = T / t[2] - cnt[0];

			}

			else if (T % t[1] == 0)

			{

				if (T < t[2])

				{

					cnt[1] = T / t[1];

					cnt[2] = cnt[0] = 0;

				}

				else

				{

					cnt[1] = T / t[1];

					cnt[2] = T / t[2];

					ll TT = (cnt[2] - 1) * t[2];

					cnt[0] = TT / t[0] + 1;

					cnt[1] -= cnt[0], cnt[2] -= cnt[0];

				}

			}

			else

			{

				cnt[2] = T / t[2];

				cnt[1] = T / t[1];

				ll TT = (cnt[1] - 1) * t[1];

				cnt[0] = TT / t[0] + 1;

				cnt[1] -= cnt[0], cnt[2] -= cnt[0];

			}

			ll tot = 0;

			for (int i = 0; i < 3; i++)

				tot += cnt[i] * p[i];

			ll now = 0;

			if (tot >= h)

				now = T;

			else

				now = T + f[h - tot];

			f[h] = min(f[h], now);

		}

	}

}

int main()

{

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> p[1] >> t[1] >> p[2] >> t[2] >> H >> s;

	presolve();

	solve();

	ll ans = f[H];

	cout << ans << endl;

    return 0;

}

巴特西

Educational Codeforces Round 137 (Rated for Div. 2) - E. FTL

DP

题意

思路

代码

最新文章

热门文章