//PKU  P10283(To The Max),等价于二维最大子段和 
#include<iostream>
using namespace std;
#define N 101
int number[N][N],temp[N];
int n;
void init(void)
{
     //freopen("input.in","r",stdin);
     //freopen("output.out","w",stdout);
     cin>>n;
     for(int i=1;i<=n;i++)
     {
             for(int j=1;j<=n;j++)
             {
                     cin>>number[i][j];
             }
     }
     return;
     
}
void work(void)
{
     int maxn=0;
     for(int x=1;x<=n;x++)
     {
             for(int y=x;y<=n;y++)
             {
                     for(int z1=1;z1<=n;z1++)
                     {
                             temp[z1]=0;
                             for(int z2=x;z2<=y;z2++)
                             {
                                     
                                     temp[z1]+=number[z2][z1];
                             }
                     }
                     int b=0;
                     for(int i=1;i<=n;i++)
                     {
                             if(b>=0)b+=temp[i];
                             else b=temp[i];
                             if(b>maxn)maxn=b;
                     }
             }
     }
     cout<<maxn;
     return;
}
int main(void)
{
    init();
    work();
    //system("pause");
    return 0;
}

• Re:我用的是动态规划，AC了，大家看看能不能继续改进一下？？ (12) liuwenxian 2010-05-26 22:57:30