题解：CF46E Comb
lgx57
·
·
题解
简单前缀和优化 dp 题，写了 20 分钟就过了。
首先肯定要预处理出每一行的前缀和。用 sum_{i,j} 表示 \displaystyle\sum_{i=1}^j a_{i,j}。
接下来可以设计 dp。设 dp_{i,j} 为当前在第 i 行选了 j 个数的最大值。那么
dp_{i,j}=\begin{cases} sum_{i,j}+\displaystyle\max_{k=1}^{j-1} dp_{i-1,k} & i \bmod 2 = 1 \\ sum_{i,j}+\displaystyle\max_{k=j+1}^{m} dp_{i-1,k} & i \bmod 2 = 0\end{cases}
这样就可以前缀和优化了。每一轮计算预处理出上一次的 dp 的前缀 \max 与后缀 \max，可以把复杂度优化到 O(nm)。