poj 2029 Get Many Persimmon Trees （水题 dp）

http://poj.org/problem?id=2029
题意：一个矩形内有许多树，给你一个长和寬一定的小矩形，问最多能用小矩形盖住多少棵树
枚举求和：
 1     #include<cstdio>
 2     #include<cstring>
 3     #include<cmath>
 4     #include<iostream>
 5     #include<algorithm>
 6     #include<set>
 7     #include<map>
 8     #include<queue>
 9     #include<vector>
10     #include<string>
11     #define Min(a,b) a<b?a:b
12     #define Max(a,b) a>b?a:b
13     #define CL(a,num) memset(a,num,sizeof(a));
14     #define maxn  510
15     #define eps  1e-6
16     #define inf 9999999
17     #define mx 1<<60
18 
19     using namespace std;
20     int mat[maxn][maxn],dp[maxn][maxn];
21     int main()
22     {
23         int n, i, j,w,h,wi,hi,y,x;
24         //freopen("data.in","r",stdin);
25         while(scanf("%d",&n),n)
26         {
27             scanf("%d%d",&w,&h);
28 
29             for( i = 0 ; i <= w; ++i)
30             {
31                 for( j = 0 ; j <= h; ++j)
32                  mat[i][j] = dp[i][j] = 0;
33             }
34 
35             for( i = 0 ; i < n;++i)
36             {
37                 scanf("%d%d",&x,&y);
38                 mat[x][y] = 1;
39             }
40 
41 
42              int sum ;
43             for(i = 1; i <= w;++i)
44             {
45                 sum = 0;
46                 for( j = 1; j <= h;++j)
47                 {
48                     sum += mat[i][j];
49                     mat[i][j] = sum ;
50                 }
51             }
52 
53 
54             scanf("%d%d",&wi,&hi);
55 
56             int ans = -1 ,k;
57 
58             for(  j = 1; j <= h - hi + 1; ++j)
59             {
60                 sum = 0;
61                 for(k = 1; k <= wi; ++k)
62                    sum += mat[k][j + hi - 1] - mat[k][j - 1];
63 
64                 dp[1][j] = sum ;
65                 ans = max(ans,dp[1][j]);
66 
67             }
68             for( i = 2;  i <= w - wi + 1; ++i)
69             {
70                 for(j = 1; j <= h- hi + 1 ;++j)
71                 {
72                     dp[i][j] =dp[i - 1][j] - (mat[i - 1][j + hi - 1] - mat[i - 1][ j - 1]) + mat[i + wi - 1][j + hi - 1] - mat[i + wi - 1][j - 1];
73                     ans = max(dp[i][j],ans);
74                 }
75             }
76             printf("%d\n",ans);
77 
78 
79         }
80     }