CF82D Two out of Three

tony102

2020 年 11 月 21 日

1836 次浏览

暂无评论

1113字数

题解

[Link](https://www.luogu.com.cn/problem/CF82D)

## Sol

状态不好设, [yzhx](https://www.cnblogs.com/yzhx)讲了才会

每一轮收银都会剩下一个人没有买单,也就是说,第$x$轮结束时在 $[1, 2 * x - 1]$ 中将会有 $x$ 人剩下

每次都转移被选中的两个人似乎不好搞,就看看能不能转移那个没被选中的人.

设 $f[i][j]$ 表示第 $i$ 次买单结束以后剩下了第 $j$ 个人没有买单

那么枚举没有买单的那个人 $j$ , 这一轮买单的第 $2 \times i - 1$ 和 $2 \times i $ 个人

注意到每次转移的时候 $2 \times i - 1$ 和 $2 \times i$ 个人也有可能是被选中的,也要转移

那么转移方程式是:

$$
f[i][j] = min\{ f[i-1][j] + max(t[a], t[b]) \}
$$

$a$, $b$ 就是 $2 \times i - 1$ 和 $2 \times i$

除此之外还要记一下方案

没了

## Code

代码环节还是我最喜欢的环节

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 1e3 + 5;
const int inf = 0x7f7f7f7f;

int n;
int t[SIZE], f[SIZE][SIZE];

struct opt {
	int i, j, k;
} path[SIZE][SIZE];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

inline void output(int i, int j)
{
	if (i != 1) output(i - 1, path[i][j].k);
	if (path[i][j].i > n) { printf("%lld\n", path[i][j].j); return; }
	if (path[i][j].j > n) { printf("%lld\n", path[i][j].i); return; }
	printf("%lld %lld\n", path[i][j].i, path[i][j].j);
}

signed main()
{
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	n = read();
	for (int i = 1; i <= n; ++ i) t[i] = read();
	t[++ n] = 0;
	memset(f, inf, sizeof(f));
	f[0][1] = 0;
	for (int i = 1, a, b; i <= n / 2; ++ i) {
		a = (i << 1), b = a + 1;
		for (int j = 1; j < a; ++ j) {
			if (f[i - 1][j] + std::max(t[a], t[b]) < f[i][j]) {
				f[i][j] = f[i - 1][j] + std::max(t[a], t[b]);
				path[i][j] = (opt) {a, b, j};
			}
			if (f[i - 1][j] + std::max(t[a], t[j]) < f[i][b]) {
				f[i][b] = f[i - 1][j] + std::max(t[a], t[j]);
				path[i][b] = (opt) {a, j, j};
			}
			if (f[i - 1][j] + std::max(t[b], t[j]) < f[i][a]) {
				f[i][a] = f[i - 1][j] + std::max(t[b], t[j]);
				path[i][a] = (opt) {b, j, j};
			}
		}
	}
	printf("%lld\n", f[n / 2][n]);
	output(n / 2, n);
	return 0;
}
```

最后修改：2021 年 09 月 04 日