AtCoder Beginner Contest 210 D – National Railway(枚举,优化)_Issue!!!

LINK


选定节点 ( i , j ) (i,j) (i,j)和 ( q , w ) (q,w) (q,w),假定 i < = q & & j < = w i<=q&&j<=w i<=q&&j<=w

那么代价为

A i , j + A q , w + C ∗ ( q − i + w − j ) A_{i,j}+A_{q,w}+C*(q-i+w-j) Ai,j​+Aq,w​+C∗(q−i+w−j)

其中 ( i , j ) 造 成 的 代 价 为 (i,j)造成的代价为 (i,j)造成的代价为 A i , j − C ∗ ( i + j ) A_{i,j}-C*(i+j) Ai,j​−C∗(i+j)

而 ( q , w ) (q,w) (q,w)造成的代价为 A q , w + C ∗ ( q + w ) A_{q,w}+C*(q+w) Aq,w​+C∗(q+w)

所以我们可以枚举 ( i , j ) (i,j) (i,j)作为左上的那个点,只需要对右下的所有 ( q , w ) (q,w) (q,w)取一个最小值即可

这个可以使用二维树状数组/线段树,不过我们有更好的做法

我们枚举 ( i , j ) (i,j) (i,j)时, i i i从最后一行往上枚举, j j j从最后一列往左枚举

定义 f [ i ] [ j ] f[i][j] f[i][j]表示以 ( i , j ) (i,j) (i,j)为左上角 ( H , W ) (H,W) (H,W)为右下角的矩阵内最小权值

转移方程为 f [ i ] [ j ] = min ⁡ ( f [ i + 1 ] [ j ] , f [ i ] [ j + 1 ] , A i , j ) f[i][j]=min(f[i+1][j],f[i][j+1],A_{i,j}) f[i][j]=min(f[i+1][j],f[i][j+1],Ai,j​)

这样如果枚举 ( i , j ) (i,j) (i,j)作为左上点,那么此时最优答案是

A i , j − C ∗ ( i + j ) + min ⁡ ( f [ i ] [ j + 1 ] , f [ i + 1 ] [ j ] ) A_{i,j}-C*(i+j)+min(f[i][j+1],f[i+1][j]) Ai,j​−C∗(i+j)+min(f[i][j+1],f[i+1][j])

这样只计算了一个点在左上一个点在右下的情况

还需要做一遍一个点在左下,另一个点在右上的情况

此时维护的 f [ i ] [ j ] f[i][j] f[i][j]应该表示 ( i , j ) (i,j) (i,j)为左下角 ( 1 , W ) (1,W) (1,W)为右上角的矩阵的最小值,然后类似上面计算答案

代码就不写了…

 

本站由小牛团队全力维护,小牛十年了,大家已经步入中年 。本站源码全部经过团队成员测试并调试,价格可能比其它网站略贵几元钱,不解释!
小牛资源 » AtCoder Beginner Contest 210 D – National Railway(枚举,优化)_Issue!!!

发表评论

全站资源亲测可用,价格略高几元,不解释

立即查看 了解详情