rnqoj-93-吃西瓜-dp

num[i][j][k];  //i层,以(j,k)和(0,0)为对角围成的面积

那么num[i][j][k]=num[i][j-1][k]+num[i][j][k-1]-num[i][j-1][k-1]+ks;(ks代表第i层j行k列的数字)

在ts层上以（i,j）和(k,l)围成的面积为：num[ts][i][j]-num[ts][k][j]-num[ts][i][l]+num[ts][k][l]；

如图所示：

 

 

欲求红色的面积等于黑色框起来的面积-黄色框起来的面积-蓝色框起来的面积+绿色的面积；

这样，对于同一个（i,j）和（k,l）都能在O(1)的时间内算出来。

然后对于层次上运用最长字段和的O（n）算法，算出在高度上的最大连续数。

 

#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
#include<iostream>  
using namespace std;  
int num[51][51][51];//i层,(j,k)到(0,0)围成的面积  
int qiu[51];  
int top;  
int maxn;  
void pan()  
{  
    int ns=0;  
    int i;  
    for(i=0;i<top;i++)  
    {  
        ns+=qiu[i];  
        maxn=max(ns,maxn);  
        if(ns<0)ns=0;  
    }  
}  
int main()  
{  
    int h,m,n;  
    while(~scanf("%d%d%d",&h,&m,&n))  
    {  
        int i,j,k,l,ts;  
        for(i=1;i<=h;i++)  
        {  
            for(j=1;j<=m;j++)  
            {  
                for(k=1;k<=n;k++)  
                {  
                    int ks;  
                    scanf("%d",&ks);  
                    num[i][j][k]=num[i][j][k-1]+num[i][j-1][k]-num[i][j-1][k-1]+ks;  
                }  
            }  
        }  
        maxn=-99999999;  
        for(i=1;i<=m;i++)  
        {  
            for(j=1;j<=n;j++)  
            {  
                for(k=0;k<i;k++)  
                {  
                    for(l=0;l<j;l++)  
                    {  
                        top=0;  
                        for(ts=1;ts<=h;ts++)  
                        {  
                            qiu[top++]=num[ts][i][j]-num[ts][k][j]-num[ts][i][l]+num[ts][k][l];  
                        }  
                        pan();  
                    }  
                }  
            }  
        }  
        cout<<maxn<<endl;  
    }  
    return 0;  
}  

 

补充：软件开发 , C++ ,