例题:最大子段和问题,区间询问版本。
https://www.luogu.com.cn/problem/SP1043

考虑 dp。

\[dp_{l} = a_l \\ dp_{i} = \max(dp_{i – 1} + a_i, a_i) \]

根据矩阵乘法的重新定义,我们可以把它写成矩阵,其中“乘”->“加”,“加”->“\(\max\)”。也就是:

\[\begin{bmatrix} a_k & a_k \\ -\inf & 0\end{bmatrix} \begin{bmatrix} dp_{k-1} \\ 0\end{bmatrix} = \begin{bmatrix} dp_k \\ 0\end{bmatrix} \]

考虑求

\[\begin{bmatrix} dp_R \\ 0\end{bmatrix} \]

\[\begin{bmatrix} dp_R \\ 0\end{bmatrix} = \mathbf{A_R} \begin{bmatrix} dp_{R-1} \\ 0\end{bmatrix} = … = \mathbf{A_R}\mathbf{A_{R-1}}…\mathbf{A_{L+1}} \begin{bmatrix} a_L \\ 0\end{bmatrix} \]

也就是我们对于每次询问需要求出 $ \mathbf{A_R}\mathbf{A_{R-1}}…\mathbf{A_{L+1}}$。

怎么求?考虑我们做序列连续和怎么做。前缀和/差分;树状数组;线段树…

考虑前缀积,但是由于矩阵不一定存在逆(需要高斯消元方程有解),不行。

【待补充】

原文地址:http://www.cnblogs.com/Zeardoe/p/16915812.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性