bnds 8.26

P3117

枚举矩形上边界和下边界 \(i, j\)，然后枚举每一列 \(y\)，且必须当前列上有 \(h\) 牛，然后向右枚举直到遇到有 g 牛的列，更新最大值。注意要离散化一下坐标，再处理一下二维前缀和，时间复杂度 \(O(n^3)\)。

P3118

状压dp，设 \(f_i\) 表示当前集合为 \(i\) 时，要连续看多久电影，然后枚举不在集合 \(i\) 中的电影 \(j\)，二分找到 \(j\) 中的第一个开始时间小于 \(dp_i\) 的场次，转移即可，时间复杂度 \(O(2^n n logc)\)。

P3119

先缩点，设 \(s\) 为 1 所在的强连通分量，跑从 \(s\) 出发和到 \(s\) 的最长路。

因为只能逆行一次，所以回到 1 肯定是从1 出发到一个点 \(u\)，再从 \(u\) 逆行到一个能到 1 的点 \(v\)，所以枚举这一条逆行的边，答案即为 \(\max(f[u][0] + f[v][1] + e[u][v] - cnt[s])\)。