Gym103960I Reverse LIS 闵可夫斯基和

Problem – I – Codeforces

如果没有翻转 $k$ 次的限制,显然 LIS 一定是若干个 $0$ 后面若干个 $1$。

加上翻转 $k$ 次之后,不考虑如何翻转,只考虑原序列中什么样的子序列可以通过翻转 $k$ 次得到 $0\dots 01 \dots 1$。实际上有个很显然的结论,因为子序列一定形如 $01010101\dots$,所以只需要 $1$ 变成 $0$ 的次数不超过 $k$ 即可。

不难发现答案关于 $k$ 是凸的(斜率单调不增),并且 $k$ 的取值最多只有 $n$。因此可以用经典的分治闵可夫斯基和解决。

(细节还是比较多)

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 200005;
constexpr long long inf = 1e18;

int a[maxn], c[maxn];

vector<long long> mincowsky(const vector<long long> &a, const vector<long long> &b) {
	vector<long long> c;

	int i = 1, j = 1;
	long long tmp = a[0] + b[0];
	c.push_back(tmp);

	while (i < (int)a.size() && j < (int)b.size()) {
		if (a[i] - a[i - 1] >= b[j] - b[j - 1]) {
			tmp += a[i] - a[i - 1];
			i++;
		}
		else {
			tmp += b[j] - b[j - 1];
			j++;
		}

		c.push_back(tmp);
	}

	while (i < (int)a.size()) {
		c.push_back(tmp += a[i] - a[i - 1]);
		i++;
	}

	while (j < (int)b.size()) {
		c.push_back(tmp += b[j] - b[j - 1]);
		j++;
	}

	return c;
}

vector<vector<vector<long long> > > solve(int l, int r) {
	if (l == r) {
		vector<vector<vector<long long> > > f({vector<vector<long long> >(2), vector<vector<long long> >(2)});

		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				f[i][j].push_back(i != j ? -inf : 0);
		
		f[c[l]][c[l]][0] = a[l];
		return f;
	}

	int mid = (l + r) / 2;

	auto u = solve(l, mid), v = solve(mid + 1, r);

	
	vector<vector<vector<long long> > > f({vector<vector<long long> >(2), vector<vector<long long> >(2)});

	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++) {
			f[i][j].assign(r - l + 1, -inf);

			for (int s = 0; s < 2; s++)
				for (int t = 0; t < 2; t++) {
					auto res = move(mincowsky(u[i][s], v[t][j]));

					for (int k = 0; k < (int)res.size(); k++) {
						int p = k + (s && !t);
						
						f[i][j][p] = max(f[i][j][p], res[k]);
					}
				}
		}
	
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 1; k < r - l + 1; k++)
				f[i][j][k] = max(f[i][j][k], f[i][j][k - 1]);
	
	return f;
}

int main() {

	ios::sync_with_stdio(false);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> c[i] >> a[i];

	auto dp = solve(1, n);
	
	int q;
	cin >> q;

	while (q--) {
		int k;
		cin >> k;
		
		long long ans = 0;
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++)
				ans = max(ans, dp[i][j][min(n - 1, k)]);
		
		cout << ans << '\n';
	}

	return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇