CWOI S C0319 B 小黄鸭与数列

题意

U2FsdGVkX19NTjuIw1wbo7L4qZyBFu90Pq8dI5Skl/d1f+8F30oqANHb26BDUNgg
BwLydetQGXMEPkRjeTdSZgX4aDL+2ClT7wdOt4i7Y3XRMdIoZaiMamL6wmamlb4B
/lORW9s8Uw0HX6az3xYgtysRQilpxrZHYj0HpWX63YSsizD0tTaLT6OzREc68vnB
YmKbcRKNU76tJ4klWgoZKBlYV+/jQj8pITFC6Fn2V2AN0irnm8+3Qhqb7aRIcPfb
XuRDcexOEmCh7Zl3q9GYFiO2uNGDJLCCFS5refOh2XjYJi6fbeSaa8okZg9Z+cMj
tSS/vw1mGuhbyZHjyYF7gpBg7r5HXCFKjY4nXC75wsjcdx1DGuBKrsviSAJisYUP

解析

首先，操作一个位置，一定是先除后乘的，不可能是先乘后除。

可以设计一个 dp，令 f(i, j) 表示考虑前 i 位，第 i 位的填的值是 j，最小代价是多少。但是值域可能非常大，所以不可行。

一个非常人类智慧的优化。我们枚举一个分界点 p，表示 p 之前的位置填的值都是不小于 $2^{17}$ 的，而 p 之后的值都是大于等于 $2^{17}$ 的。对于 p 之前的位置，我们可以通过上面讲的 dp 进行计算，由于值域是 $2^{17}$，所以每个数经过操作有不超过 $17^2$ 种不同的值，复杂度 $O(17^2n)$。对于 p 之后的东西，首先，先通过一些操作将序列对齐变成 17 位，每个数有不超过 17 种不同的值，然后如果在某个位置 $a_{i} > a_{i+1}$，则 $a_{i+1}$ 后的所有值都必须乘二。容易设计一个 dp，令 g(i, j) 表示考虑后 i 位，当前位置对齐到 $2^{17}$ 的值是 j。后面的部分复杂度 $O(17n)$。最后将两个 dp 的答案合并起来即可。

#include <algorithm>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <string>
#include <vector>

using i64 = long long;
constexpr int MAXBIT = 17;
constexpr auto INF = std::numeric_limits<i64>::max() / 2;

void solve()
{
	int n;
	std::cin >> n;
	std::vector<int> a(n);
	for (auto &i : a) std::cin >> i;

	std::vector<std::vector<std::pair<int, int>>> small(n), large(n);
	std::vector<int> vis(1 << 17, -1);
	for (int i = 0; i < n; i++) {

		for (int t1 = 0; a[i] >> t1; t1++) {
			for (int t2 = 0; ; t2++) {
				int v = (a[i] >> t1) << t2;
				if (v >= (1 << 17)) {
					large[i].emplace_back(v, t1 + t2);
					break;
				} else if (vis[v] < i) {
					vis[v] = i;
					small[i].emplace_back(v, t1 + t2);
				}
			}
		}

		std::sort(small[i].begin(), small[i].end());
	}

	std::vector f(n + 1, INF), g(n + 1, INF);

	f[0] = 0;

	{
		std::vector<i64> f1(small[0].size());
		for (size_t i = 0; i < small[0].size(); i++) {
			f1[i] = small[0][i].second;
		}
		f[1] = *std::min_element(f1.begin(), f1.end());

		for (int i = 1; i < n; i++) {
			std::vector<i64> f2(small[i].size());
			i64 min = INF;
			for (size_t p = 0, q = 0; p < small[i].size(); p++) {
				while (q < small[i - 1].size() &&
				       small[i - 1][q].first <= small[i][p].first) {
					min = std::min(min, f1[q]);
					q++;
				}
				f2[p] = min + small[i][p].second;
			}
			f[i + 1] = *std::min_element(f2.begin(), f2.end());

			f1 = std::move(f2);
		}
	}

	g[n] = 0;

	{
		std::vector<i64> f1(large[n - 1].size());
		for (size_t i = 0; i < large[n - 1].size(); i++) {
			f1[i] = large[n - 1][i].second;
		}
		g[n - 1] = *std::min_element(f1.begin(), f1.end());

		for (int i = n - 1; i > 0; i--) {
			std::vector<i64> f2(large[i - 1].size(), INF);
			for (size_t p = 0; p < large[i - 1].size(); p++) {
				for (size_t q = 0; q < large[i].size(); q++) {
					if (large[i - 1][p].first <= large[i][q].first) {
						f2[p] = std::min(f2[p], f1[q] + large[i - 1][p].second);
					} else {
						f2[p] = std::min(f2[p], f1[q] + large[i - 1][p].second + n - i);
					}
				}
			}
			g[i - 1] = *std::min_element(f2.begin(), f2.end());

			f1 = std::move(f2);
		}
	}

	auto ans = INF;
	for (int i = 0; i <= n; i++) {
		ans = std::min(ans, f[i] + g[i]);
	}
	std::cout << ans << std::endl;
}

int main()
{
	int T, id;
	std::cin >> T >> id;
	while (T--) solve();
}