杰拉斯的博客

Lily's puzzle

Time Limit:1000MS Memory Limit:32768K

Description

最近lily的好朋友Kingly在农场里干活，农场里种了很多树，Kingly的任务就是：给定树的位置，然后到农场里清点树的棵数，由于他比较死板，只会一棵棵去数，所以他的工资比别人少。而lily就提醒他用计算机，因为这是计算速度最快的东东！同时lily又想到了一个问题：如果给定一个区域的尺寸，怎么样才能数出这个范围内的树最多？
举个例子，在下图中，农场是一个宽为10长为8的矩形。

每个（*） 代表一棵树。 如果给定区域的一边为4另一边为3的，那么显然是左上方的小矩形区域中的树最多，是5棵。 你的任务就是解决上述的问题！

Input

输入有多组测试数据，每组数据的格式如下： N W H x1 y1 x2 y2 ... xN yN S T N是树的总数（0<N<=500） , W 和 H 分别是农场的宽和长。 你可以假设W 和 H 是正整数他们的值不大于100。 每个i (1 <= i <= N), xi 和 yi 是第i棵树的坐标 。 你可以假设 1 <= xi <= W 和 1 <= yi <= H, 没有两棵树的位置是相同的，但是你不能假设树是以某种顺序排列好的。最后 S 和 T 是给定区域的两条边（均为整数），你可以假设 1 <= S ，T <= min(W,H)。 唯一的一个0代表输入结束。

Output

对于每组数据,请输出一个整数，代表给定区域中最多几棵树！

Sample Input

16
10 8
2 2
2 5
2 7
3 3
3 8
4 2
4 5
4 8
6 4
6 7
7 5
7 8
8 1
8 4
9 6
10 3
4 3
8
6 4
1 2
2 1
2 4
3 4
4 2
5 3
6 1
6 2
3 2
0

Sample Output

5
3

Source

ZJUT1063

穷举（TLE）：

#include<stdio.h>
#include<memory>

int a[101][101];
int b[101][101];

int Solve(int w, int h, int s, int t){
	int row, col, i, j, k, max;
	for(i = 1; i <= t; ++i){
		for(j = 1; j <= s; ++j){
			b[1][1] += a[i][j];
		}
	}
	max = b[1][1];
	for(i = 2; i <= h - t + 1; ++i){
		b[i][1] = b[i - 1][1];
		for(j = 1; j <= s; ++j){
			b[i][1] += a[i - 1 + t][j] - a[i - 1][j];
		}
		if(max < b[i][1])
			max = b[i][1];
	}
	for(k = 2; k <= w - s + 1; ++k){
		b[1][k] = b[1][k - 1];
		for(i = 1; i <= t; ++i){
			b[1][k] += a[i][k - 1 + s] - a[i][k - 1];
		}
		if(max < b[1][k])
			max = b[1][k];
		for(i = 2; i <= h - t + 1; ++i){
			b[i][k] = b[i - 1][k];
			for(j = k; j <= k + s - 1; ++j){
				b[i][k] += a[i - 1 + t][j] - a[i - 1][j];
			}
			if(max < b[i][k])
				max = b[i][k];
		}
	}
	return max;
}

int main(){
	int trees, w, h, s, t, i, j;
	while(scanf("%d", &trees) && trees){
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		scanf("%d%d", &w, &h);
		while(trees--){
			scanf("%d%d", &j, &i);
			a[i][j] = 1;
		}
		scanf("%d%d", &s, &t);
		int max = Solve(w, h, s, t);
		if(s != t){
			memset(b, 0, sizeof(b));
			int tmp = Solve(w, h, t, s);
			if(tmp > max)
				max = tmp;
		}
		printf("%d\n", max);
	}
	return 0;
}

超哥 13:51:13
算法复杂度可以降到O(N* min(S,T)) + O(WH)

你的算法是从格子计数，可以从树的角度出发，
如先考虑一个 O(N*S*T) + O(WH)复杂度的算法

即b[i][j]是左上角坐标为(i,j)格子所对应 长度为（S*T）矩阵内的树的个数，
先从树的个数做循环（输入中，把树的坐标全部压如vector）

每个数最多属于 S*T个矩阵，如果他属于b[i][j],则 b[i][j]++;

最后用一个 O(WH)的循环把b[i][j]的最大值找出来。

类似这个思路，可以推出一个更小复杂度的 O(N* min(S,T)) + O(WH)

可是又是一个TLE：

#include<stdio.h>
#include<memory>
#include<vector>
using namespace std;
int a[101][101];

struct T{
	int row, col;
	T(int row, int col):row(row), col(col){}
};

int Solve(vector<T> &v, int w, int h, int s, int t){
	int i, j, max = 0;
	memset(a, 0, sizeof(a));
	for(vector<T>::iterator it = v.begin(); it != v.end(); ++it){
		for(i = (*it).row; i > (*it).row - s && i > 0; --i){
			for(j = (*it).col; j > (*it).col - t && j > 0; --j){
				++a[i][j];
				if(a[i][j] > max)
					max = a[i][j];
			}
		}
	}
	return max;
}

int main(){
	int trees, w, h, s, t, i, j;
	while(scanf("%d", &trees) && trees){
		vector<T> v;
		scanf("%d%d", &w, &h);
		while(trees--){
			scanf("%d%d", &j, &i);
			v.push_back(T(j, i));
		}
		scanf("%d%d", &s, &t);
		int max = Solve(v, w, h, s, t);
		if(s != t){
			int tmp = Solve(v, w, h, t, s);
			if(tmp > max)
				max = tmp;
		}
		printf("%d\n", max);
	}
	return 0;
}

很神奇地，把scanf改为cin就通过了（以上两种方法都可以AC，据说是某些编译器对于cin会有所优化）：

#include<iostream>
#include<memory>
using namespace std;
int a[101][101];
int b[101][101];

int Solve(int w, int h, int s, int t){
    int row, col, i, j, k, max;
    for(i = 1; i <= t; ++i){
        for(j = 1; j <= s; ++j){
            b[1][1] += a[i][j];
        }
    }
    max = b[1][1];
    for(i = 2; i <= h - t + 1; ++i){
        b[i][1] = b[i - 1][1];
        for(j = 1; j <= s; ++j){
            b[i][1] += a[i - 1 + t][j] - a[i - 1][j];
        }
        if(max < b[i][1])
            max = b[i][1];
    }
    for(k = 2; k <= w - s + 1; ++k){
        b[1][k] = b[1][k - 1];
        for(i = 1; i <= t; ++i){
            b[1][k] += a[i][k - 1 + s] - a[i][k - 1];
        }
        if(max < b[1][k])
            max = b[1][k];
        for(i = 2; i <= h - t + 1; ++i){
            b[i][k] = b[i - 1][k];
            for(j = k; j <= k + s - 1; ++j){
                b[i][k] += a[i - 1 + t][j] - a[i - 1][j];
            }
            if(max < b[i][k])
                max = b[i][k];
        }
    }
    return max;
}

int main(){
    int trees, w, h, s, t, i, j;
    while(cin >>  trees && trees){
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        cin >> w >> h;
        while(trees--){
            cin >> j >> i;
            a[i][j] = 1;
        }
        cin >> s >> t;
        int max = Solve(w, h, s, t);
        if(s != t){
            memset(b, 0, sizeof(b));
            int tmp = Solve(w, h, t, s);
            if(tmp > max)
                max = tmp;
        }
        cout << max << endl;
    }
    return 0;
}

#include<iostream>
#include<memory>
#include<vector>
using namespace std;
int a[101][101];

struct T{
    int row, col;
    T(int row, int col):row(row), col(col){}
};

int Solve(vector<T> &v, int w, int h, int s, int t){
    int i, j, max = 0;
    memset(a, 0, sizeof(a));
    for(vector<T>::iterator it = v.begin(); it != v.end(); ++it){
        for(i = (*it).row; i > (*it).row - s && i > 0; --i){
            for(j = (*it).col; j > (*it).col - t && j > 0; --j){
                ++a[i][j];
                if(a[i][j] > max)
                    max = a[i][j];
            }
        }
    }
    return max;
}

int main(){
    int trees, w, h, s, t, i, j;
    while(cin >> trees && trees){
        vector<T> v;
        cin >> w >> h;
        while(trees--){
            cin >> j >> i;
            v.push_back(T(j, i));
        }
        cin >> s >> t;
        int max = Solve(v, w, h, s, t);
        if(s != t){
            int tmp = Solve(v, w, h, t, s);
            if(tmp > max)
                max = tmp;
        }
        cout << max << endl;
    }
    return 0;
}

志伟哥的代码，思路是遍历所有位置，每个位置从vector中找到范围内的树，每找到一个，树的数目加1，最终比较得出结果：

#include<memory>
#include<iostream>
#include<vector>
using namespace std;
struct T{
    int row, col;
    T(int row, int col):row(row), col(col){}
}; 

int Solve(int i,int j,int s,int t,vector<T> v)
{
    int suma=0;
    int sumb=0;
    for(int k=0;k<v.size();k++)
    {
        if(v[k].row<i+t && v[k].row>=i && v[k].col<j+s && v[k].col>=j)
            suma++;
        if(v[k].row<i+s && v[k].row>=i && v[k].col<j+t && v[k].col>=j)
            sumb++;
    }
    if(suma>=sumb)
        return suma;
    else
        return sumb;
}
int main()
{
    int trees, w, h, s, t, i, j;
    while(cin>>trees && trees)
    {
        vector<T> v;
        cin >> w >> h;
        while(trees--)
        {
            cin >> j >> i;
            v.push_back(T(j, i));
        }
        cin >> s >> t;
        int maxtree=0,temptree=0;
        for(int i=0;i<=w;i++)
        {
            for(int j=0;j<=h;j++)
            {
                temptree=Solve(i,j,s,t,v);
                if(temptree>maxtree)
                    maxtree=temptree;
            }
        }
        cout << maxtree << endl;
    }
    return 0;
}

三种方法运行结果如下：

可以看出遍历树更好一些，毕竟树的数量要远小于位置数量。

如需转载请注明出处：杰拉斯的博客

相关文章

• [ACM_Tyvj_1011]传纸条（双线程动态规划解法）
• [ACM_NYOJ_19]擅长排列的小明
• [ACM_NYOJ_47]过河问题
• [ACM_NYOJ_27]水池数目
• [ACM_NYOJ_8]一种排序