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;
}
三种方法运行结果如下:
Method
Result
Time(MS)
Memory(K)
Length
Language
穷举 |
Accepted
|
31 |
212 |
1197 |
G++ |
遍历树 |
Accepted
|
10 |
252 |
1114 |
G++ |
遍历位置 |
Accepted
|
13 |
288 |
1611 |
G++ |
可以看出遍历树更好一些,毕竟树的数量要远小于位置数量。
=======================签 名 档=======================
原文地址(我的博客):http://www.clanfei.com/2012/04/790.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
ACM_算法模板集史上最完整收藏版223页全免费版.pd
杭电hdu acm资料所用杭电的acm题
noi试题和解析,对于参加acm非常有帮助
浙江大学ACM题解JU_ACM_All_Anwer,里面一本非常好的chm电子书,浙大的所有ACM题及题解都在了,对学习ACM的朋友非常的好~还等什么呢?
ACM_基础篇
Pascal acm_timus_ural_1148.pas
Pascal acm_timus_ural_1099.pas
ACM__ICPC__重要补充知识.doc
ACM的重要PPT资料,对初学者非常有益处
ACM,竞赛题目,我已经在上面测试过了,可以用,题目是ARGUS,希望大家可以喜欢,花了长时间才弄好的
ACM_竞赛试题,对于那些参加各种比赛,特别是ACM大赛的人会有很大帮助
ACM_计算几何_源码.pdf
一些关于ACM算法的资料,包括5种算法的详细讲解和ACM题型分类以及一些基础题目
ACM_String.
ACM_贪心.
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
The 2014 ACM-ICPC Asia Beijing Regional Contest
ACM_Java 速成,重点讲述了JAVA的基本运用和大数类,以及JAVA中进制转化函数,对ACMer学习JAVA大有帮助
2004ACM国际大学生程序设计决赛题目
acmer pku入门题 初学acm和大一学生适合 附原题