4053 酒馆

题面

内容

你经营着 $n$ 家酒馆，第 $i$ 家酒馆可以花费 $c_{i, j}(0 \le j \le k)$ 元将这家酒馆的档次设置为 $j$。

有 $m$ 个人，每个人会在区间 $[l_i, r_i]$ 种选择一家档次最高的酒馆消费 $j$ 元（$j$ 是这家酒馆的档次），求合理设置最大每个酒馆的档次，使得收益最大化。

输入

输入第一行三个整数 $n, m, k$。

接下来 $n$ 行，每行 $k$ 个整数，第 $i$ 行第 $j$ 个数表示将酒馆 $i$ 档次设置为 $j$ 的花费，特别地，有 $c_{i, 0} = 0$，但不会在输入数据中。

接下来 $m$ 行，第 $i$ 行两个整数 $l_i, r_i$，表示第 $i$ 个人选择的酒馆区间。

输出

输出一行一个整数，表示最大收益。

样例1

输入

4 5 3
2 4 5
3 4 5
2 2 4
1 2 3
3 3
2 2
2 3
2 4
1 2

输出

7

思路

类似地，每个人会去能去的档次最高的店，定义$f_{i,j}$为只考虑$[i,j]$这个区间里的人所能得到的最大收益是什么，枚举标准最高的店$k$，定义$g_{k,t}$为有$t$人到第$k$家店，$t$为能到达$k$的人数，那么$f_{i,j}=f_{i,k-1}+f_{k+1,j}+g_{k,t}$。

$g$表示合理选择第$k$家店的档次使得收益最大的收益。

$t=S_{i,j}-S_{i,k-1}-S_{k+1,j}$

接下来就是求出所有的$g_{k,t}$，用$c_i$表示$i$的花费，$h_j$代表有$j$个人来的最高收益，也就是$g_{k,j}$。

$h_j=max(i\times{j}-c_i)$，

$i_1<i_2$

$i_1*j-c_{i_1}$

$i_2*j-c_{i_2}$

2比1优的时候，往后2都会比1优，由于2的斜率比1斜率大，交点之后2更优

假如$i_1\times{j_1}-c_1\ge{i_2\times{j_2}-c_2}$

这样处理完之后函数的斜率是单调递增的，

往后优解不一定是连续的，优先选斜率大的。

所以维护的是所有可能成为最优解的斜线，被覆盖的没必要维护（覆盖可以通过函数图像的交点位置来判断），维护可以用单调栈。

最后处理出来就是一个永远最优的分段函数。