YZOJ P3669 [USACO2008 Mar]土地购买
时间限制:1000MS 内存限制:262144KB
难度:\(6.0\) (自评)
-
题目描述
农夫 John 准备扩大他的农场,他正在考虑 \(N\) (\(1 \leq N \leq 1,000,000\)) 块长方形的土地。
每块土地的长宽满足 (\(1 \leq\) 宽 \(\leq 1,000,000\), \(1 \leq\) 长 \(\leq 1,000,000\))。每块土地的价格是它的面积,但 FJ 可以同时购买多块土地。
这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换。如果 FJ 买一块 \(3 \times 5\) 的地和一块 \(5 \times 3\) 的地,则他需要付 \(5 \times 5=25\)。
FJ 希望买下所有的土地,但是他发现分组来买这些土地可以节省经费。他需要你帮助他求出最小的经费。
-
输入格式
输入文件的第 \(1\) 行一个数 \(N\), 表示土地块数。第 \(2\) 行至第 \(N+1\) 行,每行包含两个数,表示第 \(i\) 块土地的长和宽。
-
输出格式
最小的可行费用。
-
样例输入
1 2 3 4 5 |
4 100 1 15 15 20 5 1 100 |
-
样例输出
1 |
500 |
wtcl \(O(N^2)\) 的 DP 都想不出来然后成功爆了零。
注意到土地的选择是分组的,组数没有限制,每一组可以包括的矩形也没有特殊的限制,这样范围太大了,无法进行处理。怎么办呢???
首先注意到的是,如果有出现某个矩形完全包含另一矩形的情况,那么那个小矩形就可以直接扔掉了。因为在选大矩形的同时选小矩形,那么代价不会变小;如果选择小的矩形,那么一定要选大的矩形,否则肯定是不优的。
换句话说,就是对于两个矩形 \(A, B\) ,若 \(\left(length_A \geq length_B\right) \land \left(width_A \geq width_B\right)\) ,那么矩形 \(B\) 就可以直接被删去,不需要进行处理。
处理的时候可以先以矩形的长为第一关键字,矩形的宽为第二关键字进行升序排序。因为这样随着 \(i\) 的增大,矩形的长都是非严格单调递增的,满足了 \(length_A \geq length_B\) ,所以接下来只要满足 \(width_A \geq width_B\)就可以了。(注意原序列 \(orect\) 和新序列 \(rect\) 不要搞混了)
1 2 3 4 5 6 7 8 9 |
std::sort(&orect[1],&orect[N+1]); register int nN=0; for(register int i=1;i<=N;i++) { while(nN && rect[nN].w<orect[i].w) nN--; rect[++nN]=orect[i]; } N=nN; |
这样就可以得到长非严格单增,宽非严格单减的矩形序列(注意因为删去了递增的宽,所以宽是非严格单减的)。
有了这个性质,就可以推导出DP方程了。因为长、宽都是单调的,所以显然选择连续的一些矩形作为一组购买是最优的。
所以设 \(f_i\) 为购买到第 \(i\) 个矩形时,所耗最小的费用。转移 \(f_i=\min\limits_{0 \leq j < i}\{f_j+cost_{j+1, i}\}\) 。由于长、宽单调,所以 \(cost_{j+1, i}=width_{j+1} \cdot length_{i}\) 。
状态数 \(O(N)\) ,转移费用 \(O(N)\) ,所以时间复杂度为 \(O(N^2)\) 无法通过本题。
如果是稍有知识储备的人(可惜我不是)就会立刻发现 这个是个经典的 1D1D 的 DP斜率优化模型。
对于斜率优化,orzCJKimmortalCO 揭示了一种新的方法来理解它,我会在下面进行详细说明。
这是刚才推导的转移方程: \(f_i=\min\limits_{0 \leq j < i}\{f_j+w_{j+1} \cdot l_{i}\}\) ,现在我们要赋予它以几何意义。(时刻注意,这个方程的意义是对于一个 \(i\) 在 \(0 \leq j < i\) 范围内寻找最小的 \(f_j+w_{j+1} \cdot l_{i}\))
设 \(x_j=-w_{j+1}, y_j=f_j\) ,那么需要最小化的式子就变为了 \(y_j-x_j \cdot l_i\) 。同时还注意到直线的解析式为 \(y=kx+b\) ,那么截距 \(b=y-kx\) ,所以这个需要最小化的式子其实表示的是一条斜率为 \(l_i\) 的直线的截距!
换句话说,把所有可以进行转移的 \(j\) 都表示为二维平面上的一个点 \(p_j=\left(x_j, y_j\right)\) ,我们需要做的就是在所有这样的点中,找到一个点,使经过它的斜率为 \(l_i\) 的直线的截距最小!
好的,现在想象一条斜率固定的直线从下往上平移,当它第一次经过某个点 \(p_j\) 时,这时的截距肯定取到最小值。那么这个点 \(p_j\) 在什么地方呢?显然,它会在下凸壳上。设此时这条直线的斜率为 \(k\) ,\(p_j\) 到凸壳的上一个点的直线的斜率为 \(k_1\) ,\(p_j\) 到凸壳的下一个点的直线的斜率为 \(k_2\) ,那么 \(k \in [k_1, k_2]\) 。由于下凸壳上斜率单调递增,所以在单调栈上二分决策点就可以了。
但是由于这题 \(l_i\) 是单增的,也就意味着斜率都是单增的,稍加处理后直接取队头元素即可,不需要二分。
需要稍加注意的是,这里的 \(x_j\) 也是单增的,否则就需要 CDQ分治 或者 Splay 来维护。
说实话,我觉得上面的解释实在是太好了,值得多多思考和体会。
回到本题,剩下的工作只是维护下凸壳而已。
如果队头的前两个点的直线的斜率 比 当前的斜率 \(l_i\) 还小,那么队头的那个点肯定是取不到了,因为这条直线会在到达第一个点之前先到达第二个点,所以弹出队头元素直到满足条件,这样就可以放心的取队头元素作为最小的 \(j\) 贡献给 \(i\) 。
之后就是维护下凸壳的常规操作。如果队尾两个点的直线的斜率 比 最后一个点和当前需要加入的点的直线的斜率还大,说明图形凹进去了,由于维护的是下凸壳,所以需要把队尾元素弹出直到满足条件,最后再把当前点加入。
有几个细节是值得注意的,比如要先加入 \(f_0\) 这个决策点,\(x_j=-w_{j+1}\) 等等。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <algorithm> #define MAXBFN (1<<24) char buffer[MAXBFN],*S,*T; inline char GetChar() { if(S==T) { T=(S=buffer)+fread(buffer,1,MAXBFN,stdin); if(S==T)return EOF; } return *S++; } #define _min(_a,_b) ((_a)<(_b)?(_a):(_b)) #define _max(_a,_b) ((_a)>(_b)?(_a):(_b)) inline int getnum() { register char c=GetChar(); while(!(c>='0' && c<='9')) c=GetChar(); register int a=0; while(c>='0' && c<='9') { a*=10;a+=c-'0'; c=GetChar(); } return a; } struct _rect { int l,w; bool operator < (const _rect&oth)const { return (l==oth.l?w<oth.w:l<oth.l); } }orect[1050505],rect[1050505]; struct _point { long long x,y; _point operator - (const _point&oth)const { return (_point){x-oth.x,y-oth.y}; } long long operator * (const _point&oth)const { return (x*oth.y-y*oth.x); } }pnt[1050505]; int front,rear; long long f[1050505]; int main() { register int N=getnum(); for(register int i=1;i<=N;i++) orect[i].l=getnum(),orect[i].w=getnum(); std::sort(&orect[1],&orect[N+1]); register int nN=0; for(register int i=1;i<=N;i++) { while(nN && rect[nN].w<orect[i].w) nN--; rect[++nN]=orect[i]; } N=nN; pnt[rear++]=(_point){-rect[1].w,f[0]}; for(register int i=1;i<=N;i++) { _point ts=(_point){1,rect[i].l}; while(front+1<rear && (pnt[front+1]-pnt[front])*ts>=0) front++; if(front<rear) f[i]=pnt[front].y-(long long)pnt[front].x*rect[i].l; _point tn=(_point){-rect[i+1].w,f[i]}; while(front+1<rear && (pnt[rear-1]-pnt[rear-2])*(tn-pnt[rear-1])<=0) rear--; pnt[rear++]=tn; } printf("%lld\n",f[N]); return 0; } |