[USACO19FEB]Painting the Barn G

题意

(n)个矩阵((0le x_1,y_1,x_2,y_2le 200)),可交,可以再放最多两个矩阵(这两个矩阵彼此不交),使得恰好被覆盖(k)次的位置最大。(n,kle 10^5)

做法

考虑弱化版:只能放一个矩阵
先求出不添加时的状态,发现这时候有用的位置只有(a_{i,j}={k,k-1}),故只将这个值映射到({-1,1}),其他值映射到(0)
具体的,(b_{i,j}=-[a_{i,j}=k]),然后转换成了一个求最大子矩阵的问题
用经典的方法可做到(O(200^3)),不知道这种特殊能不能更优

再考虑两个不交的矩阵
其必然是能通过一条水平直线或垂直直线切割开来,然后按上面那样做就可以了

原文地址:https://www.cnblogs.com/Grice/p/12327227.html