rnqoj-93-吃西瓜-dp - c++编程基础

又见神题。。。。

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  
#include  
#include  
#include  
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