题意: 在一个w*h宽的矩形中有些位置有树有些位置没有,然后我们须要从中选一个s*t的矩形,使得里面含有的树最多.

思路: 我们将有树位置的值看成1,其他为0,然后成了选一个区域值最大.然后考虑这个问题的一维形式,在一维的情况下,我们非常easy得到一个方案:先处理前缀和,然后就能够枚举区间端点的起点,O(1)时间计算区间和,然后取当中的最大值为答案.

这道题我们能够按相同的思路来做,先求出(1,1)到(i,j)的区间和,然后枚举起点,O(1)的时间计算区间和,取当中最大值为答案.

当然这道题由于数据量较小,全然能够暴力,还能够用二维的树状数组来做.

代码例如以下:

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define maxn 105int Map[maxn][maxn],dp[maxn][maxn];int main(){     // freopen("in.txt","r",stdin);      int w,h,s,t,n;      while(scanf("%d",&n)&&n)      {            scanf("%d%d",&w,&h);            memset(dp,0,sizeof(dp));            memset(Map,0,sizeof(Map));            for(int i=0;i
          
           w||jj>h)   continue;                     ans=max(ans,dp[ii][jj]-dp[ii][j-1]-dp[i-1][jj]+dp[i-1][j-1]);              }           printf("%d\n",ans);      }  return 0;}