主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF1810G The Maximum Prefix
最后更新于 2025-08-27 21:24:04
作者
BPG_ning
分类
题解
题解
CF1810G
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
为什么最大前缀和想不到倒着做！tell me why！ 如上述，对于求最大前缀和一个很好的想法是从后往前扫，维护 $s$ 表示当前 $[i,n]$ 的最大前缀和，然后 $s\gets \max(s+a_i,0)$，这样只需要维护一个变量，在 dp 时也只需要维护一个状态。 考虑回答 $[1,l]$ 的答案，相当于从 $(l,0)$ 开始走，从 $(i,j)$ 以 $p_i$ 概率走到 $(i-1,j+1)$，以 $1-p_i$ 的概率走到 $(i-1,\max(j-1,0))$，走到 $(0,i)$ 的答案是 $h_i$，暴力 dp 回答一个答案的时间复杂度是 $O(n^2)$ 的。 由于多组询问的起点会变，但是终点是不变的，考虑从终点倒着往起点走，直接 dp 即可。总时间复杂度 $O(n^2)$。
正在渲染内容...
点赞
0
收藏
0
