HDU1244 最大连续子字段和最终加强版

记录 $dp[i][j]$ 表示以第 $i$ 个元素结尾，有 $j$ 组的时候的最大和，那么有

$$dp[i][j]=\max\{dp[k][j-1]\}+sum[i-l_j+1][i]$$

其中 $k+l_j \leq i$，那么这样的转移是 $O(n)$ 的，为了优化，记录 $s[i][j]$ 表示 $s[0][j]$ 到 $s[i][j]$ 中的最大 dp 值，那么可以在 $O(1)$ 的时间内做到转移，最后可以得到一个转移方程：

$$dp[i][j]=s[i][j-1]+sum[i-l_j+1][i]。$$

注意 $sum$ 数组可以用前 $n$ 项和得到。

我的代码中用 $val$ 直接表示前 $n$ 项和。

我的代码：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX = 1200;
int dp[MAX][25], s[MAX][25], l[MAX], val[MAX];

int main() {
  int n, m;
  while (scanf("%d", &n), n) {
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
      scanf("%d", &l[i]);
    }
    val[0] = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%d", &val[i]);
      val[i] += val[i - 1];
    }
    memset(dp, 0, sizeof(dp));
    memset(s, 0, sizeof(s));
    for (int j = 1; j <= m; j++) {
      for (int i = 1; i <= n; i++) {
        if (i - l[j] >= 0) {
          dp[i][j] = s[i - l[j]][j - 1] + val[i] - val[i - l[j]];
        }
        s[i][j] = max(s[i - 1][j], dp[i][j]);
      }
    }
    int ret = 0;
    for (int i = 1; i <= n; i++) {
      ret = max(ret, dp[i][m]);
    }
    printf("%d\n", ret);
  }
  return 0;
}