题解：P2418 yyy loves OI IV

这是半个乱搞做法。

首先我一开始读错题了，没有考虑到整个宿舍膜拜同一个人的情况。

下面一段是部分的正解，也是这篇题解的侧重点。

设膜拜 yyy 的人是

1

, 膜拜 c01 的人是

-1

。此时一个区间的和是区间中膜拜 yyy 的人数减去膜拜 c01 的人数。计算前缀和。

状态定义：

dp_i

表示前

i

个人，最小的宿舍数量。

暴力是

O(n^2)

的。考虑优化。

考虑一个合法区间

j + 1 \sim i

，

\lvert{sum_i - sum_j}\rvert \le m

，拆开可得

sum_i - m \le sum_j \le sum_i + m

。我们其实要找的就是满足这个条件的最小的

dp_j

。那很好了，我们直接把

dp_i

丢到一颗线段树里面，具体地，点

sum_i

，值

dp_i

，查

sum_i-m \sim sum_i+m

。单点修改，区间查询，好写。

70pts

CPP

#include<iostream>
#include<algorithm>
using namespace std;
int n, m, bn;
int a[500010], sum[500010], mx[500010], mn[500010], b[1500010];
int tr[3000010], dp[500010];
void build(int u, int l, int r) {
	tr[u] = 1e9;
	if(l == r) return ;
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
}
void insert(int u, int l, int r, int x, int k) {
	tr[u] = min(tr[u], k);
	if(l == r) return ;
	int mid = l + r >> 1;
	if(x <= mid) insert(u << 1, l, mid, x, k);
	else insert(u << 1 | 1, mid + 1, r, x, k);
}
int query(int u, int l, int r, int x, int y) {
	if(x <= l && r <= y) return tr[u];
	int mid = l + r >> 1;
	int ans = 1e9;
	if(x <= mid) ans = min(ans, query(u << 1, l, mid, x, y));
	if(y > mid) ans = min(ans, query(u << 1 | 1, mid + 1, r, x, y));
	return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		if(a[i] == 2) a[i] = -1;
		sum[i] = sum[i - 1] + a[i];
		b[++bn] = sum[i]; b[++bn] = sum[i] - m; b[++bn] = sum[i] + m;
	}
	sort(b + 1, b + bn + 2);
	bn = unique(b + 1, b + bn + 2) - b - 1;
	for(int i = 0; i <= n; i ++) {
		mx[i] = lower_bound(b + 1, b + bn + 1, sum[i] + m) - b;
		mn[i] = lower_bound(b + 1, b + bn + 1, sum[i] - m) - b;
		sum[i] = lower_bound(b + 1, b + bn + 1, sum[i]) - b;
	}
	build(1, 1, bn);
	insert(1, 1, bn, sum[0], 0);
	for(int i = 1; i <= n; i ++) {
        dp[i] = query(1, 1, bn, mn[i], mx[i]) + 1;
		insert(1, 1, bn, sum[i], dp[i]);
	}
	cout << dp[n] << '\n';
	return 0;
}

你注意到三个 WA 的点数据范围不大。

然后就是乱搞了。

CPP

for(int i = 1; i <= n; i ++) {
    dp[i] = query(1, 1, bn, mn[i], mx[i]) + 1;
    for(int j = i - 1; j >= 1; j --) {
        if(a[j] == a[j + 1]) dp[i] = min(dp[i], dp[j - 1] + 1);
        else break;
    }
    insert(1, 1, bn, sum[i], dp[i]);
}

O(n^2)

开 O2 过了。

这个情况的正解可以直接用数组记一下，这里就不再赘述了，非常简单，自己写吧。

题解：P2418 yyy loves OI IV

文章操作

相关推荐

评论

题解：P2418 yyy loves OI IV