Description：

$n$ 个城市，第 $i$ 辆车从 $s_i$ 出发到 $t_i$ ，每公里耗油 $c_i$ ，最多加 $r_i$ 次油，问油箱最大的车油箱最小是多少。

$1\leqslant n\leqslant 400,1\leqslant q\leqslant 250000$

Solution：

怎么看都像二分，但是实际上是区间 $DP$ ， $f[l][r][d]$ 表示 $l$ 到 $r$ 分成 $d$ 段最长段最短是多少，转移枚举最后一段左端点： $$ f[l][r][d]=\min(\max(f[l][pos][d-1],a[r]-a[pos])) $$ 随着 $r$ 变大 $pos$ 也单调变大，因此固定 $l$ 转移 $r$ 双指针扫 $pos$ 就可以优化到 $O(n^3)$ ，卡空间所以要压一维。

Code：

#include<bits/stdc++.h>

using namespace std;

int n,m;

#define MAXN 410

int a[MAXN];

int d[MAXN][MAXN];

#define MAXQ 250010

struct query

{

	int s,t,c,r;

}q[MAXQ];

bool cmp_s(query a,query b){return a.s < b.s;}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

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

	{

		scanf("%d%d%d%d",&q[i].s,&q[i].t,&q[i].c,&q[i].r);

		q[i].r = min(q[i].r + 1,n);

	}

	sort(q + 1,q + 1 + m,cmp_s);

	long long ans = 0;

	for(int l = 1,cur = 1;l <= n;++l)

	{

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

		d[l][0] = 0;

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

		{

			int pos = l;

			for(int r = l + 1;r <= n;++r)

			{

				while(pos < r && max(d[pos + 1][k - 1],a[r] - a[pos + 1]) < max(d[pos][k - 1],a[r] - a[pos]))++pos;

				d[r][k] = max(d[pos][k - 1],a[r] - a[pos]);

			}

		}

		while(cur <= m && q[cur].s == l)

		{

			ans = max(ans,1ll * d[q[cur].t][q[cur].r] * q[cur].c);

			++cur;

		}

	}

	cout << ans << endl;

	return 0;

}