Description：

一栋大楼，第 $i$ 个人会在 $T_i$ 时间到达，到达第 $k_i$ 层，上下电梯不要时间，电梯移动一层需要 $1$ 单位时间，问最少多少时间可以使得电梯送完所有人回到 $0$ 层。

$1\leqslant n\leqslant 10^5$

Solution：

首先可以列一个 $O(n^2)$ 的 $1D/1D$ 的动态规划 $f[i]=\max(\max(t[i],f[j])+2\times \max(k[j+1]\sim k[i]))$ ，这个可以用线段树优化 $DP$ ，具体来说就是用线段树维护 $\max(k[j+1]\sim k[i])$ ，再维护一个 $f[j]+2\times \max(k[j+1]\sim k[i])$ 的值，然后就可以转移了，感觉会非常难写，但是实际上可以用决策单调性，虽然把这题的决策点打表出来会发现其实没有决策单调性，但是我们发现如果有一个人他要到的楼层比一个在他之后的人低，那这个人就是没用的，所以可以用单调栈把所有这样的人都删掉，然后转移方程为 $f[i]=\max(f[j]+\max(t[i]-f[j],0)+2\times k[i])$ ，然后把四边形不等式的式子列出来，会发现 $k[i]$ 的项可以消掉，然后分类讨论一下 $t[i],t[i+1],f[j],f[j-1]$ 的六种大小情况会发现满足四边形不等式，于是决策单调性就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

typedef long long ll;

ll f[MAXN];

ll t[MAXN],h[MAXN];

ll w(int i,int j)

{

	return max(f[j],t[i]) + 2 * h[j + 1];

}

struct state

{

	int l,r,p;

}q[MAXN];

int head,tail;

int getpos(int l,int r,int a,int b)

{

	int mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(w(mid,a) >= w(mid,b))r = mid;

		else l = mid + 1;

	}

	return l;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%lld%lld",&t[i],&h[i]);

	}

	int tot = 0;

	for(int i = 1;i <= n;++i)

	{

		while(tot > 0 && h[i] >= h[tot])--tot;

		++tot;h[tot] = h[i];t[tot] = t[i];

	}

	n = tot;

	memset(f,0x3f,sizeof(f));

	f[0] = 0;

	head = 1;tail = 0;

	q[++tail] = (state){1,n,0};

	for(int i = 1;i <= n;++i)

	{

		while(i > q[head].r)++head;

		f[i] = w(i,q[head].p);

		int l;

		while(head <= tail && w(q[tail].l,i) <= w(q[tail].l,q[tail].p))--tail;

		if(w(q[tail].r,i) <= w(q[tail].r,q[tail].p))

		{

			l = getpos(q[tail].l,q[tail].r,q[tail].p,i);

			q[tail].r = l - 1;

			if(q[tail].l > q[tail].r)--tail;

			q[++tail] = (state){l,n,i};

		}

		else

		{

			l = q[tail].r + 1;

			if(l <= n)q[++tail] = (state){l,n,i};

		}

	}

	cout << f[n] << endl;

	return 0;

}