Codeforces Round #666 (Div. 1)

A-Multiples of Length

题意

给一个序列，每回可以选择一个区间，并给这个区间的每个数都减去这个区间长度的倍数（每个减去的数可以不同，但都是区间长度的倍数）。

构造一种方案使得每个位置的数都被减成 0. 并且只能选择三个区间。

题解

小清新智力题。

选择 \(1\) 到 \(n-1\) 这个区间，可以将每个数减去 \(a(n-1)\) 。

代码

B-Stoned Game

题意

有若干堆石子，每队石子有 \(a_i\) 个。现在两人玩一个游戏，每次可以在一堆石子里取 1 个，但与上回取石子的那个人不能取同一堆石子。

题解

设 \(x=\max_{i=1}^n a_i,s=\sum_{i=1}^n a_i\) ，那么若 \(x> \frac{s}{2}\) ，必是先手获胜。这时先手只要不断取最多的那堆石子就可以获胜。

下面证明 \(s\) 是偶数并且 \(x\ge\frac{s}{2}\) 的时候，必然是后手胜。

设一共有 \(s\) 个石子。如果能将这 \(s\) 个石子两两配对，那么先手拿任何一个石子，后手只要拿与之配对的棋子即可。将所有石子标上编号，那么将编号为 \(i\) 的石子与编号为 \(i+\frac{s}{2}\) 的石子配对。

C-Monster Invaders

题解

\(f_{i,0/1}\) 表示：

• 现在在第 \(i\) 层。
• 第 \(i-1\) 层的 Boss 的血量为 \(0/1\) 。
• 从第 \(i\) 层开始（包含第 \(i\) 层），以后每一层都没有打过。
• 满足以上条件打法的最小代价。

转移：

\(f_{i,0}\) 的转移：

• 将第 \(i\) 层的小怪都用手枪杀死，并用 AWP 将 Boss 打爆。转移到 \(f_{i+1,0}\) 。
• 将第 \(i\) 层的小怪、大怪都用 手枪/激光枪 全部打掉一滴血，并跳到 \(i+1\) 层，转移到 \(f_{i+1,1}\) 。

\(f_{i,1}\) 的转移：

• 直接跳回 \(i-1\) 层并将第 \(i-1\) 层的 Boss 杀死，再跳回到第 \(i\) 层。转移到 \(f_{i,0}\)。
• 先将 \(i\) 层的所有怪物都减掉一滴血（使用激光枪或手枪），再回到第 \(i-1\) 层杀死 Boss，再回来杀掉第 \(i\) 层的 Boss。此时已经将第 \(i\) 层的所有怪物都杀死，转移到 \(f_{i+1,1}\) 。

答案：

• \(f_{n+1,0}-d\)
• \(f_{n,0}+x\) ，其中 \(x\) 这样计算：
  • 手枪+AWP杀死第 \(n\) 层所有怪物
  • 或者 激光枪/手枪+手枪 先将第 \(n\) 层所有怪物打掉一滴血，然后跳到 \(n-1\) 层再跳回来并打死 Boss 的最小代价。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int NN = 1e6 + 5;
int N;
ll f[NN][2], A[NN], r1, r2, r3, d;
void Upd(ll &x, ll y) {
	if (x > y)
		x = y;
}
int main() {
	scanf("%d%lld%lld%lld%lld", &N, &r1, &r2, &r3, &d);
	for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);
	memset(f, 0x3f, sizeof(f));
	f[1][0] = 0;
	for (int i = 1; i <= N; ++i) {
		Upd(f[i][0], f[i][1] + 2*d + r1);
		Upd(f[i+1][0], f[i][1] + min((A[i]+1)*r1, r2) + d + r1 + d + r1 + d);
		Upd(f[i+1][0], f[i][0] + A[i]*r1 + r3 + d);
		Upd(f[i+1][1], f[i][0] + min(r2, (A[i]+1)*r1) + d);
	}
	printf("%lld\n", min(f[N+1][0] - d, f[N][1] + r1*A[N] + r3 + d + r1));
	return 0;
}