土地征用题解(兼斜率优化详解)

现在我们得到了一个高度单调递减，宽度单调递增的矩形序列对吧
那么是不是很容易发现一定是把一段下标连续的矩形并购更优
简单证明一下：如果并购不连续，那么中间那个断开的高度一定小于前一段，宽度一定小于后一段，把它并购到这一段不连续的里面不会产生费用，所以这种决策不会更差，只会更优。。。

\(dp\)部分

有前面的那个简单性质，可以考虑\(dp\)了
设\(dp[i]\)表示买完前i块矩形的最小费用
显然有\(dp\)方程：\(dp[i]=min_{j=2}^i\){\(dp[j-1]+h[j]*w[i]\)}
表示我们把区间\([i,j]\)上的矩形并购了

斜率优化

由来

直接做肯定是\(O(n^2)\)的复杂度
考虑优化
那么假设我们有\(j\)和\(k\)两个可能的转移状态，不妨设\(j>k\)
那么假设决策\(j\)比决策\(k\)更优，我们看要满足什么条件
\[ dp[j-1]+h[j]*w[i]<=dp[k-1]+h[k]*w[k] \]合并同类项化简之后会得到
\[ \frac{dp[j-1]-dp[k-1]}{h[j]-h[k]}=>w[i] \]嗯？这个式子怎么这么眼熟？这就是为什么我们叫他斜率优化

实现

是不是只要满足上面那个式子，决策\(j\)就一定优于决策\(k\)
那么我们把\((h[j],dp[j-1])\)看做一个点,那么上面式子的左边可以看做点\(j\)和\(k\)的斜率
而由于\(w[i]\)是单调不降的
所以我们的那个斜率要求单调递增（相等的话决策结果一样就不考虑了），并且大于等于\(w[i]\)对吧
这个可以用单调队列来维护
在队尾每次把点\(i\)加入其中，条件是与队尾的点斜率大于队尾与队尾-1的点(维护斜率单调递增)
在队首每次查询，条件是队首的斜率满足要求（大于\(w[i]\)(同样相等不考虑了)）
可能讲起来还很抽象，借助代码。。。
\(calc\)是按照上面的“斜率”定义来求斜率的函数
\(k[tl-1]\)表示队列中\(Q[tl-1]\)与\(Q[tl]\)的斜率
\(ljl[i].w\)就是\(w[i]\)辣。。。定义一个结构体而已。。。

    int hd=1,tl=0;for(int i=1;i<=n;++i){while(hd=calc(i,Q[tl]))--tl;k[tl]=calc(i,Q[tl]),Q[++tl]=i;while(hd

#include
#define lst long long
#define ldb double
#define N 50050
using namespace std;
const int Inf=1e9;
int read()
{int s=0,m=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return m?-s:s;
}int n;
ldb k[N];
int Q[N];
lst dp[N];
struct Land{lst h,w;}ljl[N];
bool cmp(const Land &a,const Land &b){return a.h==b.h?a.w>b.w:a.h>b.h;}
ldb calc(int x,int y){return (dp[x-1]-dp[y-1])/(ljl[y].h-ljl[x].h);}
int main()
{n=read();for(int i=1;i<=n;++i)ljl[i]=(Land){read(),read()};sort(ljl+1,ljl+n+1,cmp);int L=1;for(int i=1;i<=n;++i)if(ljl[L].w=calc(i,Q[tl]))--tl;k[tl]=calc(i,Q[tl]),Q[++tl]=i;while(hd

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！