poj1050经典DP的二维形式

题目大意就是给出一个n×n的矩阵，要求在里面找一个子矩阵，使得子矩阵中的元素和是最大的，输出这个最大的元素和

解决这题首先要会求给n个数，问这n个数的最大子串和是多少？这一道题就是把上面的问题拓展到了二维，但解决方法类似

枚举所有的行组合，将这些行压缩成一个数列，进行上述操作就可以了

poj1050 To the Maxview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[105][105];
int sum[105];
int dp[105];
int main()
{
    int n ;
    while ( cin >> n )
    {
        int i , j , k , t;
        for ( i = 0 ; i < n ; i ++ )
            for ( j = 0 ; j < n ; j ++ )
                cin >> a[i][j] ;
        int sumall = - (1 << 30 );
        for ( i = 0 ; i < n  ; i ++ )
        {
            int sumdp;    
            for ( t = i + 1 ; t <= n ; t ++ )
            {
                for ( j = 0 ; j < n ; j ++ )
                {
                    int sumi = 0 ;
                    for ( k = i ; k < t ; k ++ )
                    {
                        sumi += a[k][j] ;
                    }
                     sum[j] = sumi ;
                    if ( j )
                        sumall = max ( sumall , sumdp = max ( sumdp + sum[j] , sum[j] ) ) ;
                    else
                       sumall = max ( sumall , sumdp = sum[j] ) ;
                }
            }
        }
        cout << sumall << endl ; 
    }
    return 0 ;
}