Ruins He's house

有很多的方法过这题，以下介绍三种方法，主要思路是将序列反转（其实不反转也没什么），然后去找第 $i$ 个元素左边靠最右的比这个元素大的位置 $j$，那么 $i-j+1$ 就是第 $i$ 个元素对应的解。

典型的单调队列优化 dp。对于 $n$ 类物品，某类物品的数量为 $k$，价值为 $v$，容量为 $w$。那么考虑到这个种类的物品的时候有如下 dp 方程：

设 $dp[i]$ 表示容量为 $i$ 的时候得到的最大价值，那么我们就有：

$$dp[i]=\max\{dp[i-k \times w]+k \times v\}$$

换一种写法:

$$dp[mod+k \times w]=\max\{dp[mod+j \times w]+(k-j) \times v\}$$

这里为了方便，我们用 $s_j$ 表示 $dp[mod+j \times w]$，所以就有

$$dp[mod+k \times w]=\max\{s_j + (k-j) \times v\} = \max\{s_j-j \times v\}+k \times v$$

这里 $k$ 已经是定值，也就是说 $dp[mod+k \times w]$ 只和一定范围内的 $s_j-j \times v$ 的最大值有关，可以用单调队列优化。总的复杂度是 $O(N \times V)$ 的。

这道题比较简单，由于价值都是 1 的，我们就直接开一个 bool 型数组存储是否存在解就可以了。然后枚举到的 $k$ 如果 $dp[k]$ 是可达的，那么我们就将其 id 入队，否则就不管，另外由于价值一样，所以不要记录价值。

此类背包问题还可以进一步地优化，如果 $k$ 等于 $1$ 的时候直接写 0-1 背包，如果物品可以取得的总容量大于背包总容量，那么就直接写完全背包，因为这两种写法和单调队列相比常数小了非常多。

最后考虑到很大的输入输出量，选择 C++ 编译器。

这题是单调队列的典型运用。

至于单调队列，就是一个双端队列，在队首 ($f$) 出队，在队尾 ($b$) 出队入队，我们要维护整个队列的元素是单调的，比如，我们要动态查询从左向右的区间的最小值，那么我们就要在队列中维护一个单调递增的序列，从左向右枚举，队列的元素还有一个 $id$ 值，代表这个元素在原序列中的位置，然后左边的元素如果不在范围内了，就判断队首的元素 $id$ 是否是这个左边的 id，是的话就出队，否则就不管。关于元素入队，首先判断入队的元素是否大于队尾的元素 (保证队列单调递增)，如果不大于，那么弹出队尾元素，直到队尾元素小于入队元素或者队列为空。

枚举 $sum[i]$ 表示前 $i$ 个元素的和，注意这里为了实现循环的序列要将 $n$ 扩展到 $2n$。
然后枚举每一个 $sum[i]$，找到 $i$ 之前 $k$ 个元素 $[i-k, j]$ 区间内的 $sum$ 最小值 $sum[k]$，$sum[i] - sum[k]$ 就是最优解，然后取全局最优解即可。
注意一点在队列中在处理队列之前就要先将 $i - k - 1$ 号元素删除，我们要在队列维护最多 $k + 1$ 个元素，然后去最值，最后才将 $sum[i]$ 入队。
复杂度 $O(n)$。

这道题当初想当然的认为 LCIS 只要求出 LCS 记录路径然后求 LCS 的 LIS 就可以，发现根本不是这回事儿。。

这题很明显的 dp，但是转移方程写的各种戳。。。。- -

最裸的 dp 方程：

$$dp[i][j]=\max\{dp[k_i][k_j]\}+1$$

其中：

$$\begin{cases} k_i<i \\ k_j<j \\ a_i = a_{k_i} \\ b_j = b_{k_j} \end{cases}$$

$dp[i][j]$ 表示以 $a_i$ 和 $b_j$ 结尾的 LCIS。

这样转移正确性就不做证明了，很明显，但是转移费用太高了，是 $O(n^2)$ 的转移，这样总的时间复杂度就变成了 $O(n^4)$。对于$1000$ 的数据不可接受。

改进版本：

$$dp[i][j] = \max\{dp[k_i][j-1]\}+1$$

其中：

$$\begin{cases} ki<i \\ a_i = b_j \end{cases}$$

这时候 $dp[i][j]$ 表示以 $a_i$ 结尾，$b_j$ 或其之前元素结尾的 LCIS。

这样转移就可以写成 $O(n)$ 的转移，加上 $O(n^2)$ 的状态，算法复杂度是 $O(n^3)$。

注意，这时候还有一个很显著的优化，记录一个下标 $p$ 使得 $a_p \leq b_j$ 并且 $dp[p][j-1]$ 是 $dp[0][j-1]$ 到 $dp[i-1][j]$ 中最大的，这样转移就是 $O(1)$ 的

$$dp[i][j]=dp[p][j-1]+1$$

至此，我们的 $O(n^2)$ 的 dp 方程就已经完成，总的复杂度就是 $O(n^2)$，对于 $1000$ 的数据量正好适合

这道题本来是用 dp 做的，这几天都在练 dp，看了一下，可以用线段树来做，就尝试了一下，虽然不好写，但是还是可以做的 - -。

这题的关键在于预处理出每个方格可以向左向右分别扩展多少长度，记录 $l_i$ 和 $r_i$ 分别表示第 $i$ 个格子可以向左向右扩展的格子数，那么如果选中了第 $i$ 个格子，面积就是 $(l_i + r_i + 1) \times h_i$，这样最后线性扫一遍就可以了。

$l_i$ 的求法，最直接的方法就是枚举，从该格子向左枚举，找到第一个比它小的格子，这个格子右边的都是可扩展的。

这样做复杂度是 $O(n^2)$ 的，对于 $10^5$ 的数据量来说是不可以接受的，所以我们需要优化，用线段树维护每个区间的最小值，我们会发现这个格子事实上就是 $i$ 号格子左边区间的最靠右边的比它小的格子，这样就可以轻松转化为给定区间求区间中最靠右的比 $x$ 小的元素的 $id$。

$r_i$ 的求法类似，所以要维护两棵线段树。

最后问题迎刃而解，还要注意的就是需要用到 long long 类型。。。