首页 > 代码库 > UVa108
UVa108
MaximumSum
题意:求最大子矩阵和
状态转移方程
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j]
#include <stdio.h>#include <string.h>int a[110][110], dp[110][110];int main(int argc, char *argv[]){ int n, i, j, k, g, max; while(scanf("%d", &n) != EOF) { for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) scanf("%d", &a[i][j]); max = -10000000; memset(dp, 0, sizeof(dp)); for(g = 1; g <= n; g++) for(k = 1; k <= n; k++) { for(i = g; i <= n; i++) for(j = k; j <= n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j]; if(dp[i][j] > max) max = dp[i][j]; } memset(dp, 0, sizeof(dp)); } printf("%d\n", max); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。