这段时间复习DP优化~
还是比较顺手(除了那万恶的没有单调性的斜率优化……)
# 题意
在一条街(近似地看作坐标轴)上有 n 家烧烤店,每家店都有 m 种烧烤套餐。
你现在有 m 张卷,使用第 i 张卷可以在任意店品尝一次第 i 种套餐(你也可以在一家店吃多种套餐,但是每种卷只能用一次)。
第 i 家店在位置 $x_i$,它提供的第 j 种套餐的美味值是 $w_{i,j}$。
你想品尝尽可能美味的烧烤,但是又不希望走太远的路,因此你希望知道:“品尝的所有套餐的美味值之和-行走的总距离”最大是多少。注意,你可以从任意一家店出发。
# 解析
很容易想到贪心——因为走过的店一定是连续的一个区间,所以你吃的第 j 种套餐一定是这个区间的所有饭店提供的第 j 种套餐中最美味的。而且需要走过的路程就是这个区间的长度(从左到右走一遍就可以了)。
所以可以得到,如果走过的店的区间为 $[l,r]$,则答案为:
那么对于每个 $r$,我们希望迅速地找到一个使 $f(l,r)$ 最大的 $l$。如果你试过打表,那么你会发现 $r$ 增大时,对应的使 $f(l,r)$ 最大的 $l$ 也会增大(严谨地说是“不会减小”)。但是为什么?
# 证明
不失一般性地假设 $m=1$。
设 $r_1$ 对应的左端点为 $l_1$,$r_2$ 对应 $l_2$,且 $r_1<r_2$。则需证明 $l_1\le l_2$。
记 $A=\max_{i=l_1}^{l_2-1}w_{i,1}$,$B=\max_{i=l_2}^{r_1}w_{i,1}$,$C=\max_{i=r_1+1}^{l_2}w_{i,1}$。也就是这样:看起来很像四边形不等式?Right~
首先排除掉 $A<B$ 的情况,这种情况 $r_2$ 对应 $l_1$ 会更优(懒得证明了……)也就是说 $B<A$(等号能不能不管嘛……讨论起来麻烦)
于是分类讨论:
$C<B<A$:
可得 $f(l_1,r_1)+f(l_2,r_2)=A+B-r_1-r_2+l_1+l_2=f(l_1,r_2)+f(l_2,r_1)$。
$B<C<A$:
$f(l_1,r_1)+f(l_2,r_2)=A+C-r_1-r_2+l_1+l_2$;
$f(l_1,r_2)+f(l_2,r_1)=A+B-r_1-r_2+l_1+l_2$;
所以 $f(l_1,r_1)+f(l_2,r_2)>f(l_1,r_2)+f(l_2,r_1)$
$B<A<C$:
$f(l_1,r_1)+f(l_2,r_2)=A+C-r_1-r_2+l_1+l_2$;
$f(l_1,r_2)+f(l_2,r_1)=B+C-r_1-r_2+l_1+l_2$;
所以 $f(l_1,r_1)+f(l_2,r_2)>f(l_1,r_2)+f(l_2,r_1)$;
综上,四边形不等式成立,具有单调性。
所以~ 决策单调性分治优化(你也可以写二分栈,但是这道题既然可以分治……那还是简单一点好 awa)
# 源代码
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
CSP结束回到边训练边补文化课的状态……感觉还是没有完全适应呢?