题解：P14278 [ROI 2014 Day2] 健康饮食
Nygglatho
·
·
题解
可以发现从 (1,1) 走到 (i,j) 和从 (i,j) 走到 (n,n) 是独立的，因此令 f_{i,j} 表示 (1,1) 走到 (i,j) 和 A_{i,j} 出售相同的食品的售货机最多的数量，g_{i,j} 则表示 (i,j) 走到 (n,n) 售货机最多的数量，则显然 f_{i,j}+g_{i,j}-1 即为 A_{i,j} 的冗余度。接下来仅讨论 f_{i,j} 怎么求，g_{i,j} 和 f_{i,j} 求法类似。
最直接的，对于每个食品编号 t，有 f_{i,j}=\max(f_{i,j-1},f_{i-1,j})+[A_{i,j}=t]。
想办法每次只遍历对答案有贡献的点，发现可以直接从一个位于左上的点转移到位于右下的食品编号相同的点，考虑每次直接枚举相同食品编号的点集，令食品编号为 t 的点集为 S_t，则有：f_{i,j}=\max\limits_{x\le i,y\le j,(x,y)\in S_{A_{i,j}}}f_{x,y}+1。
然后这个先排序然后对 y 坐标开个线段树维护就行了，复杂度 O(n^2\log n)。
Submission