http://poj.org/problem?id=2029
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 200 5 using namespace std; 6 7 int dp[maxn][maxn]; 8 int n,s,t,w,h; 9 int a[maxn][maxn]; 10 11 int main() 12 { 13 while(scanf("%d",&n)!=EOF) 14 { 15 if(n==0) break; 16 scanf("%d%d",&w,&h); 17 memset(dp,0,sizeof(dp)); 18 memset(a,0,sizeof(a)); 19 for(int i=1; i<=n; i++) 20 { 21 int x,y; 22 scanf("%d%d",&x,&y); 23 a[x][y]=1; 24 } 25 scanf("%d%d",&s,&t); 26 for(int i=1; i<=w; i++) 27 { 28 for(int j=1; j<=h; j++) 29 { 30 dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+a[i][j]; 31 } 32 } 33 int ans=-1; 34 for(int i=1; i<=w; i++) 35 { 36 for(int j=1; j<=h; j++) 37 { 38 int x1=i-s+1; 39 int y1=j-t+1; 40 if(x1<1||y1<1) continue; 41 ans=max(ans,dp[i][j]-dp[x1-1][j]-dp[i][y1-1]+dp[x1-1][y1-1]); 42 } 43 } 44 printf("%d ",ans); 45 } 46 return 0; 47 }