7.23 校内 test

标签：01 校内 rr ll 取反 7.23 leq test sum

T1
题面：给一个由 A,B 组成的操作序列，A 代表全部取反，B 代表 +1，每次给出操作区间 l,r 和一个 01 串，问经过操作序列中 \([l,r]\) 的操作后的 01 串，强制在线。

观察性质，发现一次取反会使后面的所有 +1 变成 -1，随便用前缀和维护即可。

T2
给一个网格图，每个格子有权值，切割一次的代价是被割网格图的大小，问全切割成 1*1 的方格的最小代价。

二维取石子，\(O(n^5)\) 区间 DP 即可。
状态：\(f_{l,r,ll,rr}\) 表示纵 \([l,r]\) 横 \([ll,rr]\) 全部分割的代价。
转移：

\[f_{l,r,ll,rr} = min\{f_{l,r,ll,k}+f_{l,r,k+1,rr}+t\},ll\leq k \leq rr-1\\ f_{l,r,ll,rr} = min\{f_{l,k,ll,rr}+f_{k + 1, r, ll, rr} + t\},l\leq k\le r-1\\ t = sum_{ll,rr} - sum_{l-1,rr} - sum_{r,ll-1} + sum_{l-1,r-1} \]

T3
P5980 [PA2019] Herbata
离谱题，考虑一种 cuan 新的思路，在保证能量守恒的前提下，用一张“银行卡”寄存多余的能量，无解就是银行卡透支或能量不守恒。

T4
咕。

标签：01,校内,rr,ll,取反,7.23,leq,test,sum
From： https://www.cnblogs.com/Lkkaknoi/p/17575240.html