[luoguP2331] [SCOI2005]最大子矩阵（DP）
传送门
orz不会做。。。
一个好理解的做法（n^3*k）：
分n=1和n=2两种情况考虑。
n=1时，预处理出前缀和sum[]。
设f[i][j]为到达第i格，已经放了j个子矩阵的最大和，
那么每次先把f[i][j]的值设为f[i1][j]（第i个元素不属于第j个子矩阵）
剩下的情况就是第i个元素属于第j个子矩阵了。
这时候用max(f[h1][j1]+(sum[i]sum[h1]), 1<=h<=i)更新f[i][j]的最大值，即枚举第j个子矩阵的起始点。
最终答案为f[m][k]。（边界条件为f[0][j]=0，包含空矩阵）
n=2时，预处理出分别列的前缀和sum1[],sum2[]。
设f[i][j][l]为在第1列到达第i格，第2列到达第j格，已经放了l个子矩阵的最大和，
那么每次先把f[i][j][l]的值设为max(f[i1][j][l],f[i][j1][l])（第i行第1列不属于子矩阵或第j行第2列不属于子矩阵，两者取较大值）
剩下的情况就是第i行第1列和第j行第2列都属于子矩阵了。
分两种情况：
一、第i行第1列和第j行第2列属于不同的子矩阵
分别枚举第i行第1列所在子矩阵的起始点和第j行第2列所在子矩阵的起始点并更新答案，
即用max(f[h1][j][l1]+(sum1[i]sum1[h1]), 1<=h<=i)和max(f[i][h1][l1]+(sum2[j]sum2[h1]),1<=h<=j)更新f[i][j]的最大值。
二、第i行第1列和第j行第2列属于同一子矩阵
仅当i==j时才包含这种情况（因为i和j要作为当前状态中子矩阵的末尾）。这时候这个子矩阵的列数必定为2。
还是一样枚举子矩阵的起始点，
在i==j的条件下用max(f[h1][h1][l1]+(sum1[i]sum1[h1])+(sum2[j]sum2[h1]),1<=h<=i)更新答案。
最后答案为f[m][m][k]（边界条件为f[0][0][l]=0，包含空矩阵）
#include <cstdio>#define M 15#define N 105 #define max(x, y) ((x) > (y) ? (x) : (y))int n, m, K;int sum[N][M];int f[N][N][M], f0[N][M];int main()if(m == 1)printf("%d\n", f0[n][K]);return 0;}for(i = 1; i <= n; i++)for(j = 1; j <= n; j++)for(k = 1; k <= K; k++)printf("%d\n", f[n][n][K]);return 0;}
还看到一个比较神的nk做法
O（Nk）时间复杂度0ms过
只有一列的不用说吧，我说下两列的
考虑每一行的状态
0 空出这一行
1 选择左边空出右边
2 选择右边空出左边
3 选择这一行两个（不作为一个矩阵，而是左边一列单独一个矩阵，右边单独一个矩阵）
4 选择这一行两个（两个一块作为一个矩阵的一部分）
定义f[i,j,k]为当前处理到第i行，已经选了j个矩阵，当前行状态为k的最大值（k为上面的04种状态）
如果空出这一行，则j不需要变化，直接继承上一行的各种状态的最大值
f[i][j][0]=max(f[i1][j][0],f[i1][j][1],f[i1][j][2],f[i1][j][3],f[i1][j][4]);
如果选择左边空出右边，如果上一行的左边没有单独地选择成为矩阵的话（即选择1或3），则j需要包含新选择成为的矩阵（即这一行的左边的这个矩阵）,
如果上一行为同时选择两列的为一个矩阵的状态，则只选择单独的左边是不能包含进去上一行的矩阵的，所以也应j1(t1为这一行左边的值)
f[i][j][1]=max(f[i1][j1][0],f[i1][j][1],f[i1][j1][2],f[i1][j][3], f[i1][j1][4])+t1;
右边同理(t2为这一行右边的值)
f[i][j][2]=max(f[i1][j1][0],f[i1][j1][1],f[i1][j][2],f[i1][j][3], f[i1][j1][4])+t2;
选择两个分别单独作为矩阵，类似只选择左边或右边，不过是单独选左边和右边合并了下
f[i][j][3]=max(f[i1][j1][1],f[i1][j1][2],f[i1][j][3])+t1+t2;
if(j>=2) f[i][j][3]=max(f[i][j][3],f[i1][j2][4]+t1+t2);
选择两个作为一个矩阵，则上一行除了可以接上的，都得j1
f[i][j][4]=max(f[i1][j1][0],f[i1][j1][1],f[i1][j1][2],f[i1][j1][3],f[i1][j][4])+t1+t2;
上一篇：Codeforces Round #345 (Div. 2) E. Table Compression（并查集）
DP