首页 > 代码库 > 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;}