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();
}