Lily's puzzle
Time Limit:1000MS Memory Limit:32768K
Description
最近lily的好朋友Kingly在農場里干活，農場里種了很多樹，Kingly的任務就是：給定樹的位置，然后到農場里清點樹的棵數，由于他比較死板，只會一棵棵去數，所以他的工資比別人少。而lily就提醒他用計算機，因為這是計算速度最快的東東！同時lily又想到了一個問題：如果給定一個區域的尺寸，怎么樣才能數出這個范圍內的樹最多？
舉個例子，在下圖中，農場是一個寬為10長為8的矩形。
![[ACM_ZJUT_1063]Lily's Puzzle](http://img.it610.com/image/product/b37944c20f144def86598a20e02b8faf.jpg)
每個（*） 代表一棵樹。 如果給定區域的一邊為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
歡迎訪問交流，至于我為什么要多弄一個博客，因為我熱愛前端，熱愛網頁，我更希望有一個更加自由、真正屬于我自己的小站，或許并不是那么有名氣，但至少能夠讓我為了它而加倍努力。。
=======================簽 名 檔=======================
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
