POJ 2029 Get Many Persimmon Trees(水题)

题意：在w*h(最大100*100)的棋盘上，有的格子中放有一棵树，有的没有。问s*t的小矩形，最多能含有多少棵树。

解法：最直接的想法，设d[x1][y1][x2][y2]表示选择以(x1, y1)为左下角，以(x2, y2)为右上角的矩形含有多少棵树。然后就可以很容易地递推了。可是空间复杂度为O(10^8)不能被接受。

　　　又发现d[x1][y1][x2][y2] = d[1][1][x2][y2] - d[1][1][x1-1][y2] - d[1][1][x2][y1-1] + d[1][1][x1-1][y1-1]，所以只需要预处理出所有的d[1][1][i][j]即可，然后每次求出一个d[x1][y1][x2][y2]就与ans比较，不用存下来。

tag:DP

 /*

  * Author:  Plumrain

  * Created Time:  2013-11-18 01:05

  * File Name: DP-POJ-2029.cpp

  */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 int n, w, h, s, t;

 bool has[][];

 int d[][][][];

 void init()

 {

     scanf ("%d%d", &w, &h);

     int t1, t2;

     CLR (has);

     for (int i = ; i < n; ++ i){

         scanf ("%d%d", &t1, &t2);

         has[t1][t2] = ;

     }

     scanf ("%d%d", &s, &t);

 }

 int DP()

 {

     int ret = ;

     CLR (d);

     ret = d[][][][] = has[][];

     for (int i = ; i <= w; ++ i)

         d[][][i][] = d[][][i-][] + has[i][];

     for (int i = ; i <= h; ++ i)

         d[][][][i] = d[][][][i-] + has[][i];

     for (int i = ; i <= w; ++ i)

         for (int j = ; j <= h; ++ j)

             d[][][i][j] = has[i][j] + d[][][i-][j] + d[][][i][j-] - d[][][i-][j-];

     for (int x1 = ; x1 <= w; ++ x1)

         for (int y1 = ; y1 <= h; ++ y1)

             for (int x2 = x1; x2 <= min(x1+s-, w); ++ x2)

                 for (int y2 = y1; y2 <= min(y1+t-, h); ++ y2)

                     ret = max(ret, d[][][x2][y2] - d[][][x1-][y2] - d[][][x2][y1-] + d[][][x1-][y1-]);

     return ret;

 }

 int main()

 {

     while (scanf ("%d", &n) != EOF && n){

         init();

         printf ("%d\n", DP());

     }

     return ;

 }