HDU 6638 – Snowy Smile

题目链接:HDU 6638

传统DP的做法是用一个数组r[u]来维护一个行前缀和,r[u]表示当第$i$行到第$j$行第$u$列所有元素相加的和,然后转化为一味的最大子段和,复杂度$O(n^3)$。

而对于题目中给出的稀疏矩阵而言,离散化之后,如果我们用线段树维护r[u],我们发现线段树最多做两千次单点更新,均摊下来每个点的复杂度很小,复杂度$O(n^2 \log n)$。

 

说点什么

avatar
50
  Subscribe  
提醒