rnqoj-93-食西瓜-dp

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;
}