FZYZ P2280 -- 艺术展览

· · 个人记录

首先，gj说得对 题目传送门

题目简述

自行理解

在一个n\times m的矩阵，每格一个正整数值a_i,_j，从(1,1)到 (n,m) ，每次选择向右或向下走，不可出界，会经过n+m−1个格子，将经过的值依次为K_1,K_2,...,K_{n+m−1}。其平均值记为K。

求{(n+m−1)\times\sum^{n+m−1} _{i=1}(K_i−K)^2}_{min}

题目实现

首先，我们会发现，要求值的式子十分繁琐，直觉告诉我们，它肯定要化简。

令 G=n+m-1 , S{=\sum^G _{i=1}K_i} , 则K=\frac{S}{G}。

&{(n+m−1)\times\sum^{n+m−1} _{i=1}(K_i−K)^2}\\ &= G\times\sum^G_{i=1}(K_i−\frac{S}{G})^2 \\&= G\times\sum^G_{i=1}(K_i^2-\frac{2K_iS}{G}+\frac{S^2}{G^2})\\&= G\times\sum^G_{i=1}K_i^2-G\times\sum^G_{i=1}\frac{2K_iS}{G}+G\times\sum^G_{i=1}\frac{S^2}{G^2}\\&= G\sum^G_{i=1}K_i^2-2S\sum^G_{i=1}{K_i}+G\times\frac{S^2}{G}\\&= G\sum^G_{i=1}K_i^2-2S^2+S^2\\&= G\sum^G_{i=1}K_i^2-S^2\\ \end{aligned}

因此

当 \sum^G_{i=1}K_i^2 一定时，S越大，原值就越小。

当 S 一定时，\sum^G_{i=1}K_i^2越小，原值就越小。

此时直觉告诉我们，后者显然更好做。

然后，聪明的你又会发现数据十分的好:

对于 100%的数据 T≤5,n≤30,m≤30,所有 ai,j≤30

导致S_{max}只有({n_{max}}+{m_{max}}-1)\times{K_{i_{max}}}= (30+30−1)×30=1770

设计f_{s,i,j}表示到(i,j)和为s的最小的G*∑(Ai^2)，最后枚举 s取 f_{s,i,j}-s^2的最小值