luogu 2331

题解

给出 $n * 1$ 的矩阵，选出 $k$ 个互不重叠的子矩阵，使得其最大
$sum[i]$ 为列的前缀和
设 $f[i][j]$ 表示前 $i$ 个数选出 $j$ 个互不重叠的子矩阵的最大价值
若第 $i$ 个数不属于第 $j$ 个矩阵 $f[i][j] = f[i - 1][j]$
否则枚举第 $j$ 个矩阵的起点 $s$，$f[i][j] = max(f[i][j], f[s - 1][j - 1] + sum[i] - sum[s - 1])$

给出 $n * 2$ 的矩阵，选出 $k$ 个互不重叠的子矩阵，使得其最大
$sum[i][1]$ 为列 $1$ 的前缀和
$sum[i][2]$ 为列 $2$ 的前缀和
$f[i][j][use]$ 表示第 $1$ 列选到的 $i$ 行，第 $2$ 列选到了 $j$ 行，选了 $use$ 个矩阵的最大价值和
考虑枚举 $i, j, use$
第 $i$ 行第 $1$ 列不属于子矩阵或第 $j$ 行第 $2$ 列不属于子矩阵
$f[i][j][use] = std:: max(f[i - 1][j][use], f[i][j - 1][use])$
第 $i$ 行第 $1$ 列和第 $j$ 行第 $2$ 列属于不同的子矩阵
分别枚举第 $i$ 行第 $1$ 列所在子矩阵的起始点和第 $j$ 行第 $2$ 列所在子矩阵的起始点并更新答案，
即
$f[i][j][use] = max (f[i][j][use], max(f[h-1][j][l-1]+(sum1[i]-sum1[h-1]), 1<=h<=i)) 和max(f[i][h-1][l-1]+(sum2[j]-sum2[h-1]),1<=h<=j)$