不得不说这题,为什么习惯把 X轴,Y轴 颠倒过来........
假设 S（X，Y） 表示以 （1，1）为左上角坐标， （X，Y）为左下角的矩形内部 树的数量， 那么有
S（X，Y） = S（X-1，Y）+ S（X，Y-1） + Vis（X，Y） // Vis 表示 X，Y点是否有树，若有则为1，否则为0
我们可以通过 O（N*M）时间预处理出 S（X，Y）
然后对于 DP（X1，Y1，X2，Y2） ： 以（X1，Y1）为左上角，（X2，Y2）为左下角的 矩形内部 树数量，有
DP（X1，Y1，X2，Y2） = S（X2，Y2） - S（X2，Y1-1）-S（X1-1，Y2）+S（X1-1，Y1-1） // 因为我们是以点为中心，一个点算做当前矩形内部，则另外矩形不包含此点，所以需要+1操作
我们可以通过 枚举 （X2，Y2） 然后 O（1）时间计算出 （X1，Y1）， O（1）时间计算出 DP（X1，Y1，X2，Y2）
总时间复杂度为 O（N*M）
解题代码
View Code #include#include #include #define MAX(a,b) (a)>(b)?(a):(b)int vis[110][110];int s[110][110], ans;int cnt, N, M, n, m;int comp( int x1, int y1, int x2, int y2 ){ //compute the number of area S( x1,y1,x2,y2 ) return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];}int main(){ while( scanf("%d", &cnt), cnt ) { memset( vis, 0, sizeof(vis) ); scanf("%d%d", &M,&N); int x, y; for(int i = 0; i < cnt; i++) { scanf("%d%d", &y,&x); vis[x][y] = 1; } scanf("%d%d", &m,&n); memset( s, 0, sizeof(s) ); // init row for(int i = 1; i <= N; i++) s[i][1] = s[i-1][1] + vis[i][1]; // init column for(int i = 1; i <= M; i++) s[1][i] = s[1][i-1] + vis[1][i]; for(int i = 2; i <= N; i++) for(int j = 2; j <= M; j++) s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1] + vis[i][j]; ans = 0; for(int i = n; i <= N; i++) for(int j = m; j <= M; j++) { int tmp = comp( i-n+1, j-m+1, i, j ); ans = MAX( ans, tmp ); } printf("%d\n", ans ); } return 0;}