连接：http://poj.org/problem?id=2029
题意：给你一个map，然后在上面种树，问你h*w的矩形上最多有几棵树~这题直接搜就可以。不能算是DP
用树状数组也可作。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <stdlib.h> 6 #include <vector> 7 #include <set> 8 #include <queue> 9 #include <stack> 10 #define loop(s,i,n) for(i = s;i < n;i++) 11 #define cl(a,b) memset(a,b,sizeof(a)) 12 using namespace std; 13 const int MAX = 155; 14 int map[MAX][MAX]; 15 int dp[MAX][MAX]; 16 17 int main(){ 18 int n, i, j, ii, jj; 19 int W, H, w, h; 20 while(cin >> n && n){ 21 memset(map, 0, sizeof(map)); 22 memset(dp, 0, sizeof(dp)); 23 cin >> W >> H; 24 while(n --){ 25 int x, y; 26 cin >> x >> y; 27 map[y][x] = 1; 28 } 29 cin >> w >> h; 30 for(i = 1; i <= H; i ++) 31 for(j = 1; j <= W; j ++) 32 dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + map[i][j]; 33 int ans = 0; 34 for(i = 1; i <= H; i ++) 35 for(j = 1; j <= W; j ++){ 36 ii = i - h + 1; 37 jj = j - w + 1; 38 if(ii < 1 || jj < 1) continue; 39 ans = max(ans, dp[i][j] - dp[ii-1][j] - dp[i][jj-1] + dp[ii-1][jj-1]); 40 } 41 cout << ans << endl; 42 } 43 return 0; 44 }