短网址生成防屏蔽,南阳网站优化排名,中职省级示范校建设网站,免费招聘人才网传送门 orz不会做。。。 一个好理解的做法#xff08;n^3*k#xff09;#xff1a; 分n1和n2两种情况考虑。 n1时#xff0c;预处理出前缀和sum[]。 设f[i][j]为到达第i格#xff0c;已经放了j个子矩阵的最大和#xff0c; 那么每次先把f[i][j]的值设为f[i-1][j]#xf…传送门 orz不会做。。。 一个好理解的做法n^3*k 分n1和n2两种情况考虑。 n1时预处理出前缀和sum[]。 设f[i][j]为到达第i格已经放了j个子矩阵的最大和 那么每次先把f[i][j]的值设为f[i-1][j]第i个元素不属于第j个子矩阵 剩下的情况就是第i个元素属于第j个子矩阵了。 这时候用max(f[h-1][j-1](sum[i]-sum[h-1]), 1hi)更新f[i][j]的最大值即枚举第j个子矩阵的起始点。 最终答案为f[m][k]。边界条件为f[0][j]0包含空矩阵 n2时预处理出分别列的前缀和sum1[],sum2[]。 设f[i][j][l]为在第1列到达第i格第2列到达第j格已经放了l个子矩阵的最大和 那么每次先把f[i][j][l]的值设为max(f[i-1][j][l],f[i][j-1][l])第i行第1列不属于子矩阵或第j行第2列不属于子矩阵两者取较大值 剩下的情况就是第i行第1列和第j行第2列都属于子矩阵了。 分两种情况 一、第i行第1列和第j行第2列属于不同的子矩阵 分别枚举第i行第1列所在子矩阵的起始点和第j行第2列所在子矩阵的起始点并更新答案 即用max(f[h-1][j][l-1](sum1[i]-sum1[h-1]), 1hi)和max(f[i][h-1][l-1](sum2[j]-sum2[h-1]),1hj)更新f[i][j]的最大值。 二、第i行第1列和第j行第2列属于同一子矩阵 仅当ij时才包含这种情况因为i和j要作为当前状态中子矩阵的末尾。这时候这个子矩阵的列数必定为2。 还是一样枚举子矩阵的起始点 在ij的条件下用max(f[h-1][h-1][l-1](sum1[i]-sum1[h-1])(sum2[j]-sum2[h-1]),1hi)更新答案。 最后答案为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()
{int i, j, k, l, x;scanf(%d %d %d, n, m, K);for(i 1; i n; i)for(j 1; j m; j){scanf(%d, x);sum[i][j] sum[i - 1][j] x;}if(m 1){for(i 1; i n; i)for(j 1; j K; j){f0[i][j] f0[i - 1][j];for(k 1; k i; k)f0[i][j] max(f0[i][j], f0[k - 1][j - 1] sum[i][1] - sum[k - 1][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){f[i][j][k] max(f[i - 1][j][k], f[i][j - 1][k]);for(l 1; l i; l)f[i][j][k] max(f[i][j][k], f[l - 1][j][k - 1] sum[i][1] - sum[l - 1][1]);for(l 1; l j; l)f[i][j][k] max(f[i][j][k], f[i][l - 1][k - 1] sum[j][2] - sum[l - 1][2]);if(i j)for(l 1; l i; l)f[i][i][k] max(f[i][i][k], f[l - 1][l - 1][k - 1] sum[i][1] - sum[l - 1][1] sum[i][2] - sum[l - 1][2]);}printf(%d\n, f[n][n][K]);return 0;
}还看到一个比较神的nk做法 ONk时间复杂度0ms过 只有一列的不用说吧我说下两列的 考虑每一行的状态 0 空出这一行 1 选择左边空出右边 2 选择右边空出左边 3 选择这一行两个不作为一个矩阵而是左边一列单独一个矩阵右边单独一个矩阵 4 选择这一行两个两个一块作为一个矩阵的一部分 定义f[i,j,k]为当前处理到第i行已经选了j个矩阵当前行状态为k的最大值k为上面的0-4种状态 如果空出这一行则j不需要变化直接继承上一行的各种状态的最大值 f[i][j][0]max(f[i-1][j][0],f[i-1][j][1],f[i-1][j][2],f[i-1][j][3],f[i-1][j][4]); 如果选择左边空出右边如果上一行的左边没有单独地选择成为矩阵的话即选择1或3则j需要包含新选择成为的矩阵即这一行的左边的这个矩阵, 如果上一行为同时选择两列的为一个矩阵的状态则只选择单独的左边是不能包含进去上一行的矩阵的所以也应j-1(t1为这一行左边的值) f[i][j][1]max(f[i-1][j-1][0],f[i-1][j][1],f[i-1][j-1][2],f[i-1][j][3], f[i-1][j-1][4])t1; 右边同理(t2为这一行右边的值) f[i][j][2]max(f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j][2],f[i-1][j][3], f[i-1][j-1][4])t2; 选择两个分别单独作为矩阵类似只选择左边或右边不过是单独选左边和右边合并了下 f[i][j][3]max(f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j][3])t1t2; if(j2) f[i][j][3]max(f[i][j][3],f[i-1][j-2][4]t1t2); 选择两个作为一个矩阵则上一行除了可以接上的都得j-1 f[i][j][4]max(f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j-1][3],f[i-1][j][4])t1t2;转载于:https://www.cnblogs.com/zhenghaotian/p/7608166.html
