洛谷P2900 [USACO08MAR]土地征用Land Acquisition（動态規劃，斜率優化，決策單調性，線性規劃，單調隊列）

洛谷題目傳送門

用兩種不一樣的思路立體地了解斜率優化，你值得擁有。

題意分析

既然所有的土地都要買，那麼我們可以考慮到，如果一塊土地的寬和高（其實是蒟蒻把長方形立在了平面上）都比另一塊要小，那麼肯定是直接并購，這一塊對答案沒有任何貢獻。

我們先把這些給去掉，具體做法可以是，按高為第一關鍵字，寬為第二關鍵字從大到小排序，然後上雙指針掃一遍。

于是，剩下的就是一個高度遞減、寬度遞增的矩形序列。考慮怎樣制定它們的并購方案會最優。顯然如果要并購，一定要挑序列中的一段區間，這樣貢獻答案的就隻有最左邊矩形的高乘上最右邊矩形的寬，中間的又是沒有貢獻了。

設\(f_i\)為前\(i\)個矩形的最小花費，\(w\)為寬，\(h\)為高，直接寫出一個\(O(n^2)\)的方程

\[f_i=\min\limits_{j=1}^i\{f_{j-1}+w_ih_j\}

\]

一看貌似是一個決策單調性優化的式子。然而。。。。。。

國中生都會的函數圖像法

這種了解方法是在決策單調性優化DP的基礎上應運而生的。

或者說，（在大多數情況下）斜率優化可以看作決策單調性優化的一種特殊情形。蒟蒻建議還是先入手決策單調性再來斜率優化吧。

蒟蒻的DP各種優化總結

蒟蒻之前寫的一道經典（裸）決策單調性題的題解戳這裡（Lightning Conductor）

對于每一個\(f_{j-1}+w_ih_j\)，我們都可以把它視為一個直線\(l_j:y=ax+b\)，其中\(a=h_j,b=f_{j-1}\)。對于每一個\(i\)，我們就是需要求出所有\(j\le i\)的直線的\(x\)取\(w_i\)時最小的一個\(y\)值。仍然用KmPlot畫一個我們需要維護的所有直線的樣子，它們應該滿足斜率依次遞減。

\(l_1:y=2x;\)

\(l_2:y=x+1;\)

\(l_3:y=\frac x 2+3;\)

\(l_4:y=\frac x 6+5.\)

真正有用的部分

這樣的話，我們就用單調隊列維護若幹個斜率遞減的函數。我們仍然需要按照決策單調性的做法，維護相鄰兩個決策直線間的臨界值（交點）\(k\)。難道還要維護決策二分棧，對每個臨界值都二分麼？

這些決策不是直線嗎？求兩個直線的交點。。。。。。國中數學就教了，是\(O(1)\)的。也就是對兩個相鄰決策直線\(l_1,l_2\)，我們求\(\frac{b_2-b_1}{a_1-a_2}\)。其它過程跟決策單調性是一模一樣的。直線入隊前，如果隊尾不滿足斜率遞增則出隊。求\(f_i\)之前，先把隊首臨界值\(\le w_i\)的決策出隊，那麼現在隊首就是最優決策了。

這樣求出\(f_n\)隻需要\(O(n)\)的時間。

高中生都會的線性規劃法

這才是了解斜率優化的正宗方法，因為上面并沒有充分展現對斜率的處理過程。

上面對兩個相鄰直線求\(\frac{b_2-b_1}{a_1-a_2}\)，看起來有點像求什麼東西。

我們原來把決策當成直線，斜率為\(a\)，截距為\(b\)。現在我們換一下。把決策\(f_{j-1}+w_ih_j\)看作一個點\(p_j(x,y)\)，其中\(x=-h_j,y=f_{j-1}\)。

現在要求解的問題又變成了什麼樣子呢？在平面上有若幹個點，把\(f_i\)看成目标函數\(z\)，我們需要找到\(f_i=w_ih_j+f_{j-1}\)即\(z=-w_ix+y\)的最小值。這不是個線性規劃麼？

把式子變成\(y=w_ix+f_i\)，現在就讓我們來最小化截距\(f_i\)。手(nao)動(dong)模拟一下，我們現在正在拿着一個斜率為\(w_i\)的直線，從下往上移動，當第一次經過某個決策點的時候，直線的在\(y\)軸上的截距就是我們要求的目标函數\(f_i\)的最小值了。

随便畫一堆點就可以發現，無論直線以怎樣的斜率向上靠，總有一些點永遠都不會第一次與直線相交，也就是說這些決策是沒用的。剩下的有用的決策點會構成一個凸包：（因為要畫點是以換成了GeoGebra）

凸包的性質就是斜率遞增/遞減。在此題中，因為\(w\)遞增，是以我們的單調隊列中存的是若幹個點滿足\(x\)遞增（\(h\)遞減），\(y\)遞增，而且相鄰兩個點的斜率也遞增。這和原序列的順序是同向的。假設隊尾下标為\(t\)，當需要在隊尾加入一個新的決策點時，我們可能會遇到這樣的情況：

這時候\(p_t\)已經不優了，我們把它出隊，如此直到滿足斜率遞增為止，\(p_i\)就可以入隊了。和上面那種了解方法的寫法差不多，求相鄰兩個點形成的直線斜率然後比一下大小。隊首的處理跟上面那種了解方法的寫法也差不多，如果隊首與後一個的斜率小于\(w_i\)就出隊。最後的隊首依然是最優解。

實作

兩種實作的代碼長得都差不多，都要搞一個單調隊列，都要求臨界值/斜率。是以就放一個代碼吧。。。

複雜度\(O(n\log n)\)，瓶頸竟然在sort上？！蒟蒻可不想來什麼wys排序

#include<cstdio>
#include<algorithm>
#define RG register
#define R RG int
#define G c=getchar()
#define Calc(i,j) (f[j-1]-f[i-1])/(a[i].h-a[j].h)
//method1:求出臨界值
//method2:求出斜率
using namespace std;
const int N=1e5+9;
int q[N];
double f[N],k[N];
//method1:k_i為決策直線q_i與q_i+1的臨界值（交點）
//method2:k_i為決策點q_i與q_i+1所連成直線的斜率
struct Land{
	int w,h;//結構體排序
	inline bool operator<(RG Land&x)const{
		return h>x.h||(h==x.h&&w>x.w);
	}
}a[N];
inline int in(){
	RG char G;
	while(c<'-')G;
	R x=c&15;G;
	while(c>'-')x=x*10+(c&15),G;
	return x;
}
int main(){
	R n=in(),i,h,t;
	for(i=1;i<=n;++i)
		a[i].w=in(),a[i].h=in();
	sort(a+1,a+n+1);
	for(h=i=1;i<=n;++i)//雙指針掃描去除無用矩形
		if(a[h].w<a[i].w)a[++h]=a[i];
	n=h;
	for(h=i=1,t=0;i<=n;++i){
		while(h<t&&k[t-1]>=Calc(q[t],i))--t;//維護臨界值/斜率單調
		k[t]=Calc(q[t],i);q[++t]=i;//加入決策直線/決策點
		while(h<t&&k[h]<=a[i].w)++h;//彈出已經不優的決策
		f[i]=(double)a[q[h]].h*a[i].w+f[q[h]-1];//求出最優解
	}
	printf("%.0lf\n",f[n]);
	return 0;
}