题解：CF46E Comb

简单前缀和优化 dp 题，写了 $20$ 分钟就过了。

首先肯定要预处理出每一行的前缀和。用 $sum_{i,j}$ 表示 $\displaystyle\sum_{i=1}^j a_{i,j}$。

接下来可以设计 dp。设 $dp_{i,j}$ 为当前在第 $i$ 行选了 $j$ 个数的最大值。那么

这样就可以前缀和优化了。每一轮计算预处理出上一次的 $dp$ 的前缀 $\max$ 与后缀 $\max$，可以把复杂度优化到 $O(nm)$。