https://codeforces.com/contest/1396

B. Stoned Game

 

题意：给定 n 堆石子，两人轮流操作，每次选一堆石子并从中拿掉一个，且不能选上一轮（对方轮次）选过的。拿不了的输。

博弈

如果有一堆大于其它堆之和，那么先手只要拿这堆就必赢。

否则，每次拿当前可用的最多的那堆，如果总数为奇数则先手赢，否则后手。

由于先手先选，所以后手不可能更优，所以先手输必定只能是所有石子都拿完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int n;
int a[N];
int T;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		int s = 0, mx = 0;
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]), mx = max(mx, a[i]), s += a[i];
		if (mx > s / 2)puts("T");
		else if (s & 1)puts("T");
		else puts("HL");
	}
	return 0;
}

 

C. Monster Invaders

 

题意：小怪1滴血，boss2滴血。三种武器：第一种选择对一个小怪造成1点伤害，第二种对所有该阶段的怪物（包括boss）造成1点伤害，第三种直接秒杀一个怪物（小怪或boss），三种武器每次使用的代价分别为 r1≤r2≤r3r_1\le r_2\le r_3。有 n 个阶段，每阶段有 a[i]a[i] 个小怪和 1 个boss，第一和第三种武器必须击杀该阶段所有小怪后才能对boss使用。若伤害boss但未击杀，则强制传送到相邻某个阶段，也可以在任意时候自愿传送，每次传送代价为 d。问击杀所有怪物最小总代价。

dp

dp[i]dp[i] 表示击杀前 i 个阶段所有怪物的最小代价。

每经过一个阶段必定要造成伤害，并且必定击杀所有小怪（因为留着也没用），而boss可能击杀也可能剩下 1 滴血。

试一下可以发现对于连续的阶段，从 1 到 n ，第一次每阶段都剩下一滴血，来回一次清完所有怪的代价 与 先清完 1 2，再传到 3，清完 34，再传到 5 的代价是一样的。

所以完全可以只有两种转移：第一种从 dp[i−1]dp[i-1] 转移，即前 i-1 个已经全部清完了。第二种从 dp[i−2]dp[i-2] 转移，这就要考虑利用“伤害但未击杀boss会被强制转移”这个条件来把 ii 和 i−1i-1 阶段一起清完。

主要就是分类讨论各种武器的组合方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int n;
ll r[4], d;
ll a[N];
ll dp[N];
int main() {
	scanf("%d%lld%lld%lld%lld", &n, &r[1], &r[2], &r[3], &d);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	ll g = r[1];
	dp[1] = min(a[1] * r[1] + r[3], min((a[1] + 1)*r[3], r[2] + 2 * d + g));
	for (int i = 2; i <= n; i++) {
		ll f1 = min(r[2], r[1] * (a[i - 1] + 1)), f2 = min(r[2], r[1] * (a[i] + 1));	//留1滴血
		ll h = min(a[i] * r[1] + r[3], min(r[2] + 2 * d + g, r[1] * (a[i] + 1) + 2 * d + g));	//击杀boss
		dp[i] = dp[i - 1] + d + h;
		ll tmp = (i - 2 == 0 ? 0 : d);
		ll t1 = f1 + d + f2 + d + g + d + r[1];
		ll t2 = f1 + d + h + d + g + d;
		if (i == n)t2 -= d;
		tmp += min(t1, t2);
		dp[i] = min(dp[i], dp[i - 2] + tmp);
	}
	printf("%lld\n", dp[n]);
	return 0;
}