Luogu – P2900 – Land Acquisition

题目描述

翻译的不是很好,所以我简化一下题面。

给定 $n$ 个矩阵的宽 $w$ 和高 $h$,每次选一个矩阵集合,代价为集合中的 $\max{\{w\}}\times \max{\{h\}}$。

任意两次之间没有重复的矩阵,求取完所有矩阵的最小代价

定义

矩阵的两个参数为 $w, h$,分别对应下图中的宽和高。

函数 $\operatorname{slope}(i, j)$ 表示 $(x_i, y_i)$ 与 $(x_j, y_j)$ 构成的直线的斜率,$x, y$ 的含义在下面会说。

分析

注意到对于两个矩阵 $i, j$,如果 $w_i\leq w_j$ 并且 $h_i\leq h_j$,那么 $i$ 和 $j$ 一定可以放到一组,$i$ 对答案没有贡献,不用考虑,可以直接删去。

比如下图当中的 $1$ 和 $2$. 矩阵 $2$ 能完全被 $1$ 包含,所以 $2$ 没有贡献,可以删去。

P2900-1

于是考虑先删除所有 $i$ 这样的矩阵。

具体做法就是:按照 $h$ 为第一关键字,$w$ 为第二关键字从大到小排序,之后双指针扫一遍即可。

//a已经降序排序
int t = 0;
for(int i = 1; i <= n; i++) {
	if(a[i].w > a[t].w) a[++t] = a[i];
}

如上图,剩下的只有 $1, 3$ 号矩阵。

删完之后剩下的就是一个,$h$ 严格单调递减,$w$ 严格单调递增的序列。考虑 $DP$ 解决。

DP

设 $f_i$ 为新序列中,取走前 $i$ 个矩阵的最小花费,$w$ 为宽(单调递增),$h$ 为高(单调递减),那么有转移方程:

$$
f_i=\min_{j=0}^{i}{\{f_{j}+w_ih_{j+1}\}}
$$

相当于,把 $j+1$ 到 $i$ 这一段合为一组取走。由于单调性,所以这一组的 $\max{\{w\}}=w_i$,$\max{\{h\}}=h_{j+1}$.

复杂度 $\mathcal{O}(n^2)$。这显然可以斜率优化。

斜率优化

我们目前优化的目的,是尽快地找到 $f_i$ 到底是由哪个 $j$ 转移过来的,也就是尽快找到最小化 $f_i$ 的继承状态。

为了表示方便,设 $j$ 为能使 $f_i$ 最小化的继承状态,所以有:

$$
f_i=f_{j}+w_ih_{j+1}
$$

考虑一次函数斜截式 $y=kx+b$ 或 $b=y-kx$,将状态转移方程变换为这个形式:

$$
f_{j}=-w_ih_{j+1}+f_i
$$

其中变量 $x, y$ 与 $j$ 有关,$b, k$ 与 $j$ 无关。且要求 $x$ 随 $j$ 单调递增,$b$ 中包含 $f_i$(斜率优化基本操作)。

所以可以构造出直线方程为:

$$
\left\{
\begin{array}{lr}
y = f_j\\
k = w_i\\
x = -h_{j+1}\\
b = f_i
\end{array}
\right.
$$

我们把 $(x, y)$ 看成平面直角坐标系上的点。那么现在 $(x_j, y_j)$ 的意义就是:直线 $y=kx+b$ 上的一个点

又因为我们的目的是最小化 $f_i$,在上面的表示当中,$f_i$ 只与直线的截距 $b$ 有关。所以显然地,问题转化为:如何选取 $j$ ,才能使得过点 $(x_j, y_j)$ 的直线的截距 $b$ 最小。

20190701195640154

显然,对于一个斜率 $k$ 来说,最优解 $j$ 就是从左往右枚举到的第一个 $\operatorname{slope}(j, j+1)>k$ 的点。(其中 $\operatorname{slope}$ 的定义在上面有说过)

再考虑单调性: $x$ 随 $j$ 单调递增,$k$ 随 $i$ 单调递增,要使截距 $b=f_i$ 最小。

显然,所有的最优决策点 $j$ 都在下凸包上,也就是上图中的折线。

所以单调队列维护下凸包即可:

设单调队列(递增)为 $q$,队首为 $head$,队尾为 $tail$,当前要转移 $i$ 号点,那么具体步骤:

  1. 当 $\operatorname{slope}(q_{head}, q_{head+1})\leq w_i=k_i$ 时,$head$++,(保证最优解)
  2. 此时的 $q_{head}$ 就是最优转移点,根据它和转移方程计算出 $f_i$,
  3. 当 $\operatorname{slope}(q_{tail-1}, q_{tail})\geq\operatorname{slope}(q_{tail}, i)$ 时,$tail$–,(维护下凸包
  4. 在队尾插入 $i$.

代码

#include <bits/stdc++.h>
#define X(i) (-a[i+1].h)
#define Y(i) (f[i])
#define int long long
using namespace std;
const int MAXN = 5e4 + 10;
int n;
struct Node{
	int w, h;
} a[MAXN];
int f[MAXN];
bool cmp(Node i, Node j) {
	return (i.h > j.h) || (i.h == j.h && i.w > j.w);
}
double slope(int i, int j) {
	return (Y(j) - Y(i)) / (double)(X(j) - X(i));
}
int head, tail, q[MAXN];
signed main() {
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld%lld", &a[i].w, &a[i].h);
	}
	sort(a + 1, a + n + 1, cmp);
	int t = 0;
	for(int i = 1; i <= n; i++) {
		if(a[i].w > a[t].w) a[++t] = a[i];
	}
	n = t;
	head = tail = 1;
	for(int i = 1; i <= n; i++) {
		while(head < tail && slope(q[head], q[head + 1]) <= a[i].w) {
			head++;
		}
		int j = q[head]; f[i] = f[j] + a[i].w * a[j + 1].h;
		while(head < tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i)) {
			tail--;
		}
		q[++tail] = i;
	}
	cout << f[n] << endl;
	return 0;
}
暂无评论

发送评论 编辑评论

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